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

문제 링크

---

🔷 분류

자료 구조, 그래프 이론, 최단 경로, 데이크스트라, 우선순위 큐

✒️ 문제 설명

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

⬅️ 입력

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

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

도시의 번호는 $1$번부터 $n$번까지 연속하여 붙어 있으며, $1$번 도시는 시작도시이다. 두 도로의 시작점과 도착점이 모두 같은 경우는 없다.

➡️ 출력

 $n$

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

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

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> node;
int n, m, k;
int A[1001][1001];
priority_queue<int> dist[1001];
priority_queue<node, vector<node>, greater<node>> q; // <거리, 노드>

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> k;
  for(int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    A[a][b] = c;
  }

  // Dijkstra
  q.push({0, 1});
  dist[1].push(0); // 1번 노드의 첫 번째 경로

  while(!q.empty()) {
    auto now = q.top();
    q.pop();

    for(int nex = 1; nex <= n; nex++) {
      if(A[now.second][nex] != 0) { // 간선 존재
        int newCost = now.first + A[now.second][nex];

        if(dist[nex].size() < k) { // k개 미만 저장되어 있으면 추가
          dist[nex].push(newCost);
          q.push({newCost, nex});
        }
        else if(dist[nex].top() > newCost) { // k개 있지만 더 좋은 경로면 교체
          dist[nex].pop();
          dist[nex].push(newCost);
          q.push({newCost, nex});
        }
      }
    }
  }

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