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

1854 K번째 최단 경로 찾기

문제

---

봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.

입력

---

첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n. 1 ≤ c ≤ 1000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.

출력

---

n개의 줄을 출력한다. i번째 줄에 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

---

풀이)

기본적인 다익스트라 풀던 것처럼 풀면서, 시간만 따로 저장했더니 틀린 문제이다.

기존처럼 풀면 최단 경로만 찾게 되니깐, k번째 경로의 시간은 pass 해버릴 수 있다.

푸는 방법을 변형해야했다. 경로를 여러 개를 저장해야 하므로 풀이과정은 이러하다.

1. 각 정점마다 시간을 저장할 우선순위 큐를 할당한다.

2. 다익스트라를 돌리면서 현재 정점에서 도로을 통해 가는 next 정점과 next 정점을 가는 시간을 확인 

   next 정점의 큐가 k 크기보다 작다면, 큐에 시간을 삽입 그리고 그 시간으로 또 다익스트라 진행

                             같다면, 큐에 저장된 시간 중 최대 시간을 확인 

-> 새로운 시간이 최대 시간보다 작다면

    최대 시간을 새로운 시간으로 update

    그리고 새로운 시간으로 다익스트라 진행

  (우선순위 큐는 내림차순이 기본 설정이므로, 

   최대 시간은 우선순위 큐의 top()이다)

3. 1번 정점부터 k번째 시간 출력

    (큐의 크기가 k보다 작다면, k번째 최단 경로를 찾지 못했다는 것이니깐 -1 출력)

코드)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 999999999
int n, m, k;
vector<pair<int, int>> adj[1001];
priority_queue <int> dist[1001];
 
//1번도시에서 다른 도시들까지의 소요시간 저장
void dijkstra() {
    priority_queue <pair<int, int>> qu;
    qu.push({ 0,1 });
    dist[1].push(0); //1번도시에서 1번 도시는 시간 0 걸림
 
    while (!qu.empty())
    {
        int here = qu.top().second;
        int cost = -qu.top().first;
        qu.pop();
        
        for (int i = 0; i < adj[here].size(); i++) {
            int next = adj[here][i].first;
            int next_cost = adj[here][i].second + cost;
            //만약 next정점에 아직 k번째까지의 길이가 없다면 바로 저장
            if (dist[next].size() < k) {
                dist[next].push(next_cost);
                qu.push({ -next_cost,next });
            }
            //next정점에 k번째 최단거리까지 이미 저장되어있는데
            //현 k번째 거리보다 새로운 거리가 더 짧을 경우
            else if (dist[next].top() > next_cost) {
                dist[next].pop();
                dist[next].push(next_cost);
                qu.push({ -next_cost,next });
            }
            
        }
    }
}
 
int main() {
 
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b,c });
    }
    dijkstra();
    
 
    for (int i = 1; i <= n; i++) {
        if (dist[i].size() < k) printf("-1\n");//k번째 경로가 없다면
        else printf("%d\n", dist[i].top());
    }
    return 0;
}