백준 1753번 - 최단경로

www.acmicpc.net/problem/1753

1753번: 최단경로

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
 
using namespace std;
typedef pair<int, int> node;
 
int V, E; //V: 정점의 개수, E: 간선의 개수
int sp;
bool visited[20001];
int dist[20001];
vector<node> graph[20001];
priority_queue<node, vector<node>, greater<node> >PQ;
 
void Dijkstra(int p)
{
    PQ.push(node(dist[p], p));
    while (!PQ.empty())
    {
        int curr = PQ.top().second;
        PQ.pop();
        for (node &np : graph[curr])
        {
            int pos = np.first;
            int    dis = np.second;
            if (dist[pos] > dist[curr] + dis)
            {
                dist[pos] = dist[curr] + dis;
                PQ.push(node(dist[pos], pos));
            }
 
        }
    }
 
}
 
int main()
{
    scanf("%d %d %d", &V, &E, &sp);
    for (int i = 0; i < E; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back(make_pair(v, w));
    }
 
    for (int i = 1; i <= V; i++)
        dist[i] = 2e9;
    
    dist[sp] = 0;
    Dijkstra(sp);
 
    for (int i = 1; i <= V; i++)
    {
        if (dist[i] == 2e9)
            printf("INF\n");
        else
            printf("%d\n", dist[i]);
    }
 
    return 0;
}