[Dijkstra]BOJ 1854_K번째 최단경로 찾기

문제 링크 : www.acmicpc.net/problem/1854

1854번: K번째 최단경로 찾기

 

다익스트라 알고리즘을 적용해 각 정점에 대한 K번째 최단경로의 가중치 합을 구하는 문제이다.

일반적인 다익스트라 알고리즘에서는 우선순위 큐(최소 힙)에서 pop되는 순간

그 정점에 대한 최소 가중치 합은 고정된다. (다익스트라 알고리즘 참조 : 4legs-study.tistory.com/21)

다익스트라 알고리즘은 기본적으로 최단거리를 구하는 알고리즘이기 때문에,

한 번 힙에서 꺼내진 정점에 대해서는 다시 고려하지 않는다.

힙에서 꺼내진 정점에 대한 가중치 합이 현재 기록된 최소 가중치보다 같거나 작아야 하기 때문이다.

 

다익스트라에서 이 조건을 없앤다면 어떻게 될까?

최소 힙에 의해 각 정점에 대한 경로의 가중치 합이 오름차순으로 계속 pop 될 것이다.

이 중에서 K번째에 해당하는 최소 가중치 합을 찾으면 된다.

 

어떤 한 정점의 K번재 최단경로를 구하기 위해 다른 연결된 정점에 대해서도

K번째 최단경로까지만 구하면 될까? 혹시 K번째 이후의 정보가 필요하지 않을까?

라는 의문이 들 수 있다.

위에서 언급했듯 각 정점에 대한 가중치 합은 오름차순으로 나타나므로,

어떤 정점 V에 대해 V의 K번째 최단경로는 반드시 V와 연결된 모든 다른 정점들의 K번째 최단경로들 중

하나에 의해 결정되므로, 모든 다른 정점에 대해 K번째까지만 최소 가중치 합을 구하면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
#define INF 9999999999999
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n, m, k;
int cnt[1001];    //각 노드에 대해 발견한 최단거리 갯수를 저장 : 값이 8이라면 8번째 최단경로
vector<p> adj[1001];
ll dist[1001];
 
void dijkstra() {
    priority_queue<pair<ll, int>> pque;
    pque.push({ 0, 1 });
 
    while (!pque.empty()) {
        pair<ll, int> cur = pque.top();
        pque.pop();
 
        ll distval = -cur.first;
        int node = cur.second;
 
        if (dist[node] == INF) {
            cnt[node]++;
            if (cnt[node] == k) dist[node] = distval;
            for (int i = 0; i < adj[node].size(); i++) {
                int next = adj[node][i].first;
                ll newDist = distval + adj[node][i].second;
                if(dist[next] == INF)
                    pque.push({ -newDist, next });
            }
        }
    }
}
 
void init() {
    int a, b, c;
    cin >> n >> m >> k;
 
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        adj[a].push_back({ b, c });
    }
 
    for (int i = 1; i <= n; i++) dist[i] = INF;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    dijkstra();
 
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) printf("-1\n");
        else printf("%lld\n", dist[i]);
    }
 
    return 0;
}