CSES 1196 - Flight Routes

你的任務是找出從 Syrjälä 到 Metsälä 的 \(k\) 條最便宜航班路線。一條路線可以多次經過同一座城市。

注意可能有多條路線的票價相同，這些路線都必須各自列出（見範例）。

輸入格式

第一行有三個整數 \(n\)、\(m\) 和 \(k\)：城市數、航班數與參數 \(k\)。城市依序編號為 \(1,2,\ldots,n\)。城市 \(1\) 是 Syrjälä，城市 \(n\) 是 Metsälä。

接下來有 \(m\) 行描述航班。每行有三個整數 \(a\)、\(b\) 和 \(c\)：表示一段航班從城市 \(a\) 出發，抵達城市 \(b\)，票價為 \(c\)。所有航班皆為單向航班。

你可以假設從 Syrjälä 到 Metsälä 至少存在 \(k\) 條相異路線。

輸出格式

輸出 \(k\) 個整數：依票價排序後最便宜的 \(k\) 條路線的票價。

範例輸入 1

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

範例輸出 1

4 4 7

說明：最便宜的路線分別是 \(1 \rightarrow 3 \rightarrow 4\)（票價 \(4\)）、\(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\)（票價 \(4\)）與 \(1 \rightarrow 2 \rightarrow 4\)（票價 \(7\)）。

限制

• \(2 \le n \le 10^5\)
• \(1 \le m \le 2 \cdot 10^5\)
• \(1 \le a,b \le n\)
• \(1 \le c \le 10^9\)
• \(1 \le k \le 10\)

題目來源

CSES - Flight Routes

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。