1854 K번째 최단경로 찾기

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

각 정점의 1번 도시로 부터의 K번째 최단 경로의 소요시간를 찾는 문제이다. 각 정점마다 소요시간들을 저장할 우선순위 큐(Priority Queue)를 할당한다. 그리고 다익스트라를 돌리면서 만약에 해당 정점의 큐의 크기가 K보다 작다면 시간을 그냥 추가해주고 K까지 꽉찼다면 큐의 top(최대값)과 비교하여 새로운 시간이 더 작다면 기존 값을 pop해주고 새로운 값을 넣어주면 된다. 우선순위 큐를 이용하는 이유는 현재까지의 최대 소요시간을 빠르게 찾기 위해서이다. 배열을 사용하면 새로운 거리를 추가하는데 O(1)이 걸리지만 최대값을 찾을 때마다 O(N)이 걸리기 때문에 비효율적이다. 우선 순위 큐를 사용하면 추가하는데 O(logN), 찾는데 O(1)이 걸리기 때문에 훨씬 효율적이다.

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