백준[1916] - 최소비용 구하기

문제

백준 1916 문제 보기

접근 방법

한 정점에서 모든 정점을 최소비용으로 가는 방법을 구하는 문제이므로 이는 다익스트라 알고리즘을 활용해 해결할 수 있다.

즉, 구하고자하는 마을과 버스 노선을 그래프로 그려 이를 활용해 우선순위 큐로 문제를 해결한다.

코드

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;
 
// N: 마을 수, M: 버스 노선 수, source: 출발, destination: 목적지, dis[]: 거리
int N, M, source, destination, dis[1001];
vector<vector<pair>> graph;
priority_queue<pair<int, int>> pq;
 
int main() {
    cin >> N;
    cin >> M;
    // 그래프의 노드는 마을이므로 사이즈 증가
    graph.resize(N+1);
 
    for(int i = 0; i < M; i ++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        // 현재 마을에서 다음 마을까지의 요소를 현재 마을 인덱스에 저장
        graph[from].push_back(make_pair(to, cost));
    }
 
    cin >> source >> destination;
    // 우선순위 큐에 출발지 정보 삽입
    pq.push({0, source});
    memset(dis, -1, sizeof(dis));
 
    while(!pq.empty()) {
        // 우선순위 큐는 기본적으로 max heap을 활용하므로 - 값을 취함 
        int cost = -pq.top().first;
        int location = pq.top().second;
        pq.pop();
 
        // 이전 방문 기록이 있으면 무시
        if(dis[location] != -1) {
            continue;
        }
 
        dis[location] = cost;
 
        for(int i = 0; i < graph[location].size(); i ++) {
            int n_location = graph[location][i].first;
            // 가장 작은 비용이 상위에 저장되어야 하므로 - 값
            int n_cost = -graph[location][i].second - cost;
 
            if(dis[n_location] != -1) {
                continue;
            }
 
            pq.push({n_cost, n_location});
        }
 
    }
    cout << dis[destination];
    return 0;
}