[1854번] K번째 최단경로 찾기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 다익스트라

다익스트라와 같은데 결국 아래 코드에서 k번째 경로를 찾을 수 있다.

 if (dist[next].size() < k)

            {

                dist[next].push(nextCost + cost);

                pq.push({ nextCost + cost, adj[here][i].second });

            }

            else if (dist[next].top() > nextCost + cost)

            {

                dist[next].pop();

                dist[next].push(nextCost + cost);

                pq.push({ nextCost + cost, adj[here][i].second });

            }

dist를 우선순위 큐 배열로 만들어두고 next의 최단거리 개수가 k보다 작은 경우 계속해서 추가해주고,

그 이후로는 최단거리가 가장 큰 것들부터 계속해서 갱신해준다면 우선순위 큐에는 다음과 같이 들어있게 된다는 것이다.

next의 우선순위 큐가 1,2,3,4,5라고 하나씩 있다면 next까지 가장 최단거리가 1,2,3,4,5 순서대로 있다는 것이다.

우선순위큐가 내림차순으로 top에 존재하기에 결국 5가 5번째 최단거리가 됨을 알 수 있다.

따라서 출력에서 dist[i].size()가 k에 해당하면 top()값을 뽑아주면 정답이 된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include <iostream> #include <cstdio> #include <queue> #include <vector> #include <functional>   using namespace std;   typedef pair<int, int> pii;   const int INF = 987654321;   vector<pii> adj[1002]; priority_queue<int> dist[1002];   int main() {     int n, m, k;     scanf("%d %d %d", &n, &m, &k);       for (int i = 0; i < m; i++)     {         int from, to, val;         scanf("%d %d %d", &from, &to, &val);           adj[from].push_back({ val, to });     }       priority_queue<pii, vector<pii>, greater<> > pq;          pq.push({0, 1});     dist[1].push(0);       while (!pq.empty())     {         int here = pq.top().second;         int cost = pq.top().first;           pq.pop();           for(int i = 0 ; i < adj[here].size(); i++)         {             int next = adj[here][i].second;             int nextCost = adj[here][i].first;               if (dist[next].size() < k)             {                 dist[next].push(nextCost + cost);                 pq.push({ nextCost + cost, adj[here][i].second });             }             else if (dist[next].top() > nextCost + cost)             {                 dist[next].pop();                 dist[next].push(nextCost + cost);                 pq.push({ nextCost + cost, adj[here][i].second });             }           }     }       for (int i = 1; i <= n; i++)         dist[i].size() == k ? printf("%d\n", dist[i].top()) : printf("-1\n");     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus