최단경로

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#define INF 987654321
#define MAXX 20001
using namespace std;
 
int v, e, root;
 
typedef pair<int, int> pp;
vector<pp> edges[MAXX];
bool visited[MAXX];
int res[MAXX];
 
void dijkstra(int start) {
    priority_queue<pp, vector<pp>, greater<pp> > q;
    q.push(pp(0, start));
 
    while (!q.empty()) {
        int now = q.top().second;
        int cost = q.top().first;
        q.pop();
 
        if (visited[now]) continue;
        visited[now] = true;
 
        for (auto i : edges[now]) {
            if (!visited[i.second]) {
                if (res[i.second] > res[now] + i.first) {
                    res[i.second] = res[now] + i.first;
                    q.push(pp(res[i.second], i.second));
                }
            }
        }
    }
 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> v >> e >> root;
 
    for (int i = 1; i <= v; i++) res[i] = INF;
 
    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        edges[a].push_back(pp(c,b));
 
    }
 
    res[root] = 0;
    dijkstra(root);
 
    for (int i = 1; i <= v; i++) {
        if (res[i] == INF) cout << "INF" << '\n';
        else
            cout << res[i] << '\n';
    }
        return 0;
}