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

Approach

다익스트라의 구현을 잘 보면, 탐색 과정에서 의도적으로 최단 경로가 아닌 경우를 배제한다.

해당 경우들을 우선순위큐 자료구조로 정리하면, 쉽게 k번째 최단경로를 구할 수 있다.

 

추가적으로, 어떤 한 정점의 k번째 최단경로를 구하기 위해서 다른 정점의 k번째 최단경로 이후까지고 고려해야하는 것은 아닌지에 대한 의구심이 들 수 있다.

 

만약 특정 정점의 k + i 번째 최단경로를 활용해서 원하는 정점의 k번째 최단 경로를 구할 수 있다고 하자. 이때 최단 경로는 무조건 증가하므로 특정 정점의 k번쨰 최단 경로가 더 짧을 것이다. 따라서 k번째 정점만 모두 구해도 일반성을 잃지 않는다고 할 수 있다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, int> plli;
typedef vector <ull> ullv1;
typedef vector <vector <ull> > ullv2;
const ll INF = 2000000000;

int main() {
    fastio;
    
    int n, m, k;
    cin >> n >> m >> k;

    vector<pill> edge[1000];

    for(int i = 0; i < m; i++){
        int a, b;
        ll c;
        cin >> a >> b >> c;

        edge[a - 1].push_back({b - 1, c});
    }

    priority_queue<ll, vector<ll> > dist[1000];
    priority_queue<plli, vector<plli>, greater<plli> > pq;


    pq.push({0, 0});
    dist[0].push(0);
    
    while(!pq.empty()){
        ll cur_cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        for(auto p : edge[cur]){
            int to = p.first;
            ll cost = p.second;
            if(dist[to].size() < k){
                dist[to].push(cur_cost + cost);
                pq.push({cur_cost + cost, to});
            }
            else if(dist[to].top() > cur_cost + cost){
                dist[to].pop();
                dist[to].push(cur_cost + cost);
                pq.push({cur_cost + cost, to});
            }   
        }
    }

    for(int i = 0; i < n; i++){
        if(dist[i].size() != k){
            cout << -1 << "\n";
        }
        else cout << dist[i].top() << "\n";
    }
    return 0;
}