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

문제

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

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

 

---

알고리즘

• 다익스트라

---

풀이

다익스트라의 원리와 우선순위 큐만 잘 사용하면 쉽게 풀 수 있습니다.

 

먼저, 기본적으로 그래프를 탐색할 우선순위 큐 \(Q\)를 생성합니다. \(Q\)를 사용하는 방식은 일반적인 다익스트라에서 쓰는 방식과 같습니다.

다음으로, 우선순위 형태의 배열 \(M\)을 생성합니다. \(M_{i}\)에 \(i\)번 도시로 가는 최단경로들을 내림차순으로 저장할 것입니다. 그러면 \(M_{i}\)의 가장 뒤의 값은 현재 까지 구한 \(i\)로 가는 경로 중 \(i\)로 가는 최단경로가 되고, \(M_{i}\)의 가장 앞의 값은 현재까지 구한 \(i\)로 가는 경로 중 최장(?)경로가 됩니다.

 

이제, 기본 다익스트라를 구현할 때처럼 BFS로 탐색을 하면서 다음 작업을 수행합니다.

\(i\)는 현재 도시, \(c\)는 누적 거리, \(j\)는 \(i\)와 연결된 도시이고, \(jc\)를 \(i\)에서 \(j\)로 가는 길의 거리라고 할 때:

 

1. 만약, \(M_{j}.size() < K\)라면 \(K\)번째 최단경로가 구해지지 않았으므로, \(c + jc\)를 \(M_{j}\)에 넣고 탐색을 이어나갑니다.
   (\(M_{j}.push(c + jc); Q.push({j, c + jc});\))
2. 위 조건이 아니고, \(c + jc < M_{j}.top()\)이라면, \(M_{j}.top()\)은 K번째 최단거리가 될 수 없으므로 \(M_{j}.top()\)은 빼내고, \(c + jc\)를 집어넣습니다.
   (\(M_{j}.pop(); M_{j}.push(c + jc); Q.push({j, c + jc});\))

각각의 \(i\)에 대해서 \(M_{i}\)의 크기가 \(K\)보다 작으면 \(K\)번째 최단경로는 없으므로, \(-1\)을 출력하고, 크기가 \(K\)라면 가장 앞이 \(K\)번째 최단경로가 되므로 \(M_{i}.top()\)을 출력하면 됩니다.

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    struct Comp { bool operator()(pii &a, pii &b) { return a.y > b.y; } };
    int N, M, K; cin >> N >> M >> K;
    vector<vector<pii>> graph(N + 1);
    for (int i = 0; i < M; ++i) {
        int a, b, c; cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }
    priority_queue<pii, vector<pii>, Comp> pq;
    vector<priority_queue<int>> min_cost(N + 1);
    pq.push({1, 0}); min_cost[1].push(0);
    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        for (auto i : graph[cur.x]) {
            if (min_cost[i.x].size() < K) {
                min_cost[i.x].push(cur.y + i.y);
                pq.push({i.x, cur.y + i.y});
            }
            else if (cur.y + i.y < min_cost[i.x].top()) {
                min_cost[i.x].pop();
                min_cost[i.x].push(cur.y + i.y);
                pq.push({i.x, cur.y + i.y});
            }
        }
    }
    for (int i = 1; i <= N; ++i) {
        if (min_cost[i].size() < K) cout << "-1\n";
        else cout << min_cost[i].top() << '\n';
    }

    return 0;
}