a537. CPE：Not the Best (UVa 10740)

題目描述

給定有向加權圖、起點 x、終點 y 與 k，請求出第 k 短路徑的長度。路徑允許重複經過頂點與邊；不同走法即使長度相同，也各自占一個排名。

例如最短的數條路徑長度相同時，它們仍依出現次數計算。若總共不足 k 條從 x 到 y 的路徑，輸出 −1。

輸入格式

每組先有 n、m，2 ≤ n ≤ 100，1 ≤ m ≤ 1000，節點編號為 1 到 n。下一行有 x、y、k，x ≠ y，2 ≤ k ≤ 10。

接著 m 行各有 u、v、l，表示 u 到 v 的有向邊，0 ≤ l ≤ 10000。保證至少存在一條 x 到 y 的路徑。0 0 表示結束。

輸出格式

每組輸出一行第 k 短路徑長度；不足 k 條則輸出 -1。

題目來源：UVa 10740 — Not the Best。 原題：https://onlinejudge.org/external/107/10740.pdf