[백준 1753] 최단경로

[백준 1753] 최단경로

문제 링크

#include "header.h"
#define INF 987654321
using namespace std;
int v, e, start;
vector <pair<int, int>> vec[20001];
int dist[300001];
void input(){
    cin >> v >> e >> start;

    for(int i=0; i<e; i++){
        int from, to, cost;
        cin >> from >> to >> cost;
        vec[from].push_back({to, cost});
    }

    for(int i=0; i<v+1; i++){
        dist[i] = INF;
    }
}
void solve(){

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

    pq.push({0, start});
    dist[start] = 0;

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

        for(int i=0; i<vec[top].size(); i++){
            int next = vec[top][i].first;
            int next_cost = vec[top][i].second;

            if(next_cost + cost < dist[next]){
                dist[next] = next_cost + cost;
                pq.push({dist[next], next});
            }
        }
    }
    

    for(int i=1; i<=v; i++){
        if(dist[i] == INF) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }


}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    input();
    solve();
    return 0;
}