[BOJ] 최단경로

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define INF 987654321
#define p pair<int,int>
using namespace std;

vector<p> vc[20001];
int trace[20001];

int main(){
    memset(trace, -1, sizeof(trace));
    int v,e;
    cin >> v >> e;
    
    int st;
    cin >> st;
    
    for(int i=0; i<e; i++){
        int from, to, val;
        scanf("%d%d%d",&from,&to,&val);
        vc[from].push_back(p(to,val));
    }
    
    
    int dist[20001];
    fill(dist, dist + 20001, INF);
    dist[st] = 0;
    
    priority_queue<p, vector<p>, greater<p>> pq;
    pq.push({ 0,st });
    
    while (! pq.empty()) {
        int here = pq.top().second;
        int hereCost = pq.top().first;
        pq.pop();
        
        if(dist[here] < hereCost)
            continue;
        
        for(int i=0; i<vc[here].size(); i++){
            int next = vc[here][i].first;
            int nextCost = vc[here][i].second + hereCost;
            
            if( dist[next] > nextCost){
                dist[next] = nextCost;
                trace[next] = here;
                pq.push({ nextCost,next  });
            }
        }
    }
    
    for(int i=1; i<=v; i++){
        if( dist[i] == INF)
            printf("INF\n");
        else
            printf("%d\n",dist[i]);
    }
    
    return 0;
}