1753 최단경로

https://www.acmicpc.net/problem/1753

다익스트라 (Dijkstra) 알고리즘은 모든 간선의 가중치가 음수가 아닌 그래프에서 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘이다. 가중치가 모두 같다면 BFS로 최단거리를 구할 수 있다. 먼저 시작점으로 부터의 최단거리를 나타내는 dist 배열을 할당하고 INF로 초기화한다. 일단 시작점의 최단거리가 0임은 알 수 있다. 그 다음 우선순위 큐(최소힙)을 이용하여 지금까지 구한 정점까지의 거리 중 최소값을 빼면서 인접 정점들을 검사한다. dist 값이 갱신될 때마다 큐에 (지금까지 찾은 최단거리,정점)을 넣어준다. 이 과정을 반복하다보면 시작점으로부터 다른 모든 정점까지의 최단거리에 해당하는 간선들로 이루어진 스패닝 트리가 완성된다.

#include <cstdio>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
 
int v,e,k,a,b,c;
vector<pair<int,int>> adj[20001];
 
void dijkstra()
{
    vector<int> dist(v+1,INF);
    dist[k]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,k});
    while(!pq.empty())
    {
        int cost=-pq.top().first;
        int now=pq.top().second;
        pq.pop();
        if(dist[now]<cost) continue;
        for(auto i : adj[now])
        {
            int next=i.first;
            int ncost=cost+i.second;
            if(dist[next]>ncost)
            {
                dist[next]=ncost;
                pq.push({-ncost,next});
            }
        }
    }
    for(int i=1;i<=v;i++)
    {
        if(dist[i]==INF) printf("INF\n");
        else printf("%d\n",dist[i]);
    }
}
 
int main()
{
    scanf("%d %d %d",&v,&e,&k);
    while(e--)
    {
        scanf("%d %d %d",&a,&b,&c);
        adj[a].push_back({b,c});
    }
    dijkstra();
    return 0;
}