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';
  }
}