백준 1753 - 최단경로(C++)

문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

풀이

다익스트라 알고리즘을 이용해서 푸는 문제.

나는 다익스트라를 우선순위 큐를 이용해서 풀었는데, 이 방법은 BFS와 유사하다.

주의할 점은 우선순위 큐를 만들 때, 비용을 기준으로 Min Heap 구조가 되도록 만들어야 한다는 것이다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

위와 같이 우선순위 큐를 생성하면 first 값을 기준으로 Min Heap으로 동작한다.

이제 pq에 {비용, 정점} 쌍을 넣어주면 된다.

 

이후에는 BFS와 동일하게 큐가 빌 때까지, 인접 노드들을 방문하며 최단 거리 배열(d)를 업데이트하면 된다.

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int inf = 987654321;

vector<pair<int, int>> a[20001];
int d[20001];

void dijkstra(int start) {
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int cur = pq.top().second;
        int dis = pq.top().first;
        pq.pop();

        if (d[cur] < dis) continue;
        for (int i = 0; i < a[cur].size(); i++) {
            int next = a[cur][i].first;
            int nextDis = dis + a[cur][i].second;

            if (nextDis < d[next]) {
                d[next] = nextDis;
                pq.push({nextDis, next});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int V, E, K;
    cin >> V >> E >> K;

    fill_n(d, 20001, inf);

    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
    }
    dijkstra(K);

    for (int i = 1; i <= V; i++) {
        if (d[i] == inf) cout << "INF\n";
        else cout << d[i] << "\n";
    }
}