10740 Not the Best

題目連結

題目敘述

Abul 不是班上最優秀的學生，也不是隊上最出色的球員
這並不是說他不好；他其實真的不錯，但很不幸地，他不是最好的那一個

上個學期，我們這位「不太頂尖」的 Abul 上了一門演算法課
在其中一份作業中，他被要求找出加權有向圖中從某一給定頂點 x 到另一頂點 y 的最短路徑
你或許已經猜到了，他很少能找出最短路徑
他總是最終找到從 x 到 y 的第 k 短路徑（2 ≤ k ≤ 10）
如果他夠幸運，第 k 短的路徑與前面的所有路徑長度相同，那麼他的解答也會被認可

例如，在右側的圖中，Abul 被要求找出從頂點 5 到頂點 2 的最短路徑
從頂點 5 到頂點 2 的前 7 條最短路徑如下所示，按路徑長度遞增排序
對這個圖而言，Abul 能夠找到第 5 短的路徑，這條路徑可以是：

5 → 4 → 3 → 2 → 5 → 1 → 2，或 5 → 1 → 2 → 5 → 4 → 3 → 2

這兩條路徑的長度皆為 15

路徑	長度
5 → 1 → 2	5
5 → 4 → 3 → 2	6
5 → 1 → 2 → 5 → 1 → 2	14
5 → 4 → 3 → 2 → 5 → 1 → 2	15
5 → 1 → 2 → 5 → 4 → 3 → 2	15
5 → 4 → 3 → 2 → 5 → 4 → 3 → 2	16
5 → 1 → 2 → 5 → 1 → 2 → 5 → 1 → 2	23

給定圖的描述、起點頂點 x、終點頂點 y 及值 k，你需要找出 Abul 所計算的路徑長度。你可以假設給定圖中 x 到 y 至少存在一條路徑。

輸入說明

輸入可能包含多組測資

每組測資的第一行包含兩個整數 n（2 ≤ n ≤ 100）與 m（1 ≤ m ≤ 1000）
分別代表圖中頂點的數量與邊的數量
圖中每個頂點以 [1, n] 之間的唯一整數標識

第二行包含三個整數 x、y 和 k（1 ≤ x, y ≤ 100, x ≠ y, 2 ≤ k ≤ 10）

接下來的 m 行中，每行包含三個整數 u、v 和 l（1 ≤ u, v ≤ 100, 0 ≤ l ≤ 10000）
表示從頂點 u 指向頂點 v 的一條長度為 l 的有向邊

當 n 與 m 為兩個 0 時，輸入結束

輸出說明

對於輸入中的每組測資，輸出一行整數，表示圖中第 k 短從 x 到 y 的路徑長度
如果從 x 到 y 的路徑少於 k 條，輸出 -1

解題思路

使用修改過的 Dijkstra 的算法，也可以說是有權重的 BFS
只是這次為了求第 k 短路徑，而非最短路徑
所以不對當前節點做一次性鎖定
而是對其標記次數，當目標節點經過了第 k 次，代表其為第 k 短路徑的經過
也不管是不是已經有更短的路徑
而是把所有能夠往下走訪的節點都 push 進 priority queue
並針對經過次數超過 k 次的路徑不再展開，直接跳過

程式碼

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define PII pair<int, int>

signed main() {
    int n, m;
    while (cin >> n >> m, n+m) {
        vector<vector<PII>> g(n+1); // {連結的節點, 兩點距離}
        int x, y, k; cin >> x >> y >> k; // x：起點 y：終點 k：目標為第幾短路徑
        while (m--) { // 建圖
            int a, b, w;
            cin >> a >> b >> w;
            g[a].push_back({b, w});
        }

        vector<int> vis(n+1);
        priority_queue<PII, vector<PII>, greater<PII>> pq; // {目前距離, 當前節點}
        pq.push({0, x});
        int ans = -1;
        while (pq.size()) {
            PII now = pq.top(); pq.pop();
            if (vis[now.second]++ > k) continue; // 剪枝
            if (now.second == y && vis[now.second] == k) { // 若當前節點為終點、經過次數為 k
                ans = now.first; // 記錄下答案
                break;
            }
            for (auto &i : g[now.second]) pq.push({now.first+i.second, i.first}); // 當前節點往下走訪
        }

        cout << ans << '\n';
    }
}