[백준] 1753번 최단경로

[적용한 알고리즘]

다익스트라

 

[아이디어]

기본 예제

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

오랜만에 다익스트라를 봤다. 재밌었다.

 

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 20001;
const int INF = 1000000000;
typedef pair<int, int> P;

int main(){
    int V, E, K;
    vector<P> adj[MAX_V];
    scanf("%d %d %d", &V, &E, &K);

    for (int i = 0; i < E; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        adj[from].push_back(P(to, cost));
    }

    int dist[MAX_V];
    int prev[MAX_V];
    fill(dist, dist + MAX_V, INF);
    bool visited[MAX_V] = { 0 };
    priority_queue<P, vector<P>, greater<P>> PQ;

    dist[K] = 0;
    PQ.push(P(0, K));

    while (!PQ.empty()){
        int cur;
        do {
            cur = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[cur]);

        if (visited[cur]) break;

        visited[cur] = true;

        for (auto &p : adj[cur]){
            int nxt = p.first;
            int nxt_cost = p.second;

            if (dist[nxt] > dist[cur] + nxt_cost){
                dist[nxt] = dist[cur] + nxt_cost;
                prev[nxt] = cur;
                PQ.push(P(dist[nxt], nxt));
            }
        }
    }

    for (int i = 1; i <= V; i++){
        if (dist[i] == INF) puts("INF");
        else printf("%d\n", dist[i]);
    }
    return 0;
}