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。所有航班均为单向航班。 你可以假设至少存在 k 条从 Syrjälä 到 Metsälä 的不同路线。

输出格式

输出 k 个整数：按价格从小到大排序的 k 条最便宜路线的价格。

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

4 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$ 样例解释：最便宜的路线是 1 $\rightarrow$ 3 $\rightarrow$ 4（价格 4）、1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 4（价格 4）和 1 $\rightarrow$ 2 $\rightarrow$ 4（价格 7）。

标签: CSES1196|图论

来源

CSES1196|图论