BOJ 1753 최단경로

1 개요[ | ]

BOJ 1753 최단경로
2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

int V, E, K;
vector<pair<int,int>> A[20001];
int visited[20001] = {};

void dijkstra() {
    priority_queue<pair<int,int>> q;
    q.push({0, K});
    visited[K] = 0;
    int x, cost, nx, ncost;
    while(!q.empty()) {
        cost = -q.top().first;
        x = q.top().second;
        q.pop();
        if(visited[x] < cost) continue;
        for(auto& p: A[x]) {
            ncost = cost + p.second;
            nx = p.first;
            if(visited[nx] == -1 || visited[nx] > ncost) {
                visited[nx] = ncost;
                q.push({-ncost, nx});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> V >> E >> K;
    int u, v, w;
    for(int i=1; i<=E; i++) {
        cin >> u >> v >> w;
        A[u].push_back({v,w});
    }
    for(int i=1; i<=V; i++) {
        visited[i] = -1;
    }
    dijkstra();
    for(int i=1; i<=V; i++) {
        if(visited[i] == -1) {
            cout << "INF\n";
        } else {
            cout << visited[i] << '\n';
        }
    }
}