CSES1196 航班路线
#CS1196. 航班路线
航班路线
题目背景
翻译自 CSES-1196 题。
题目描述
你的任务是找出从 Syrjälä 到 Metsälä 的 k 条最短航班路线。一个路线可以多次经过同一个城市。
注意：可能存在多个价格相同的路线，每条这样的路线都应该被考虑（请参考示例）。
输入格式
第一行包含三个整数 n，m，和 k：分别表示城市的数量、航班的数量和需要找到的最短路线的数量 k。城市编号为 1,2,…,n1,2,…,n1,2,…,n，其中城市 1 是 Syrjälä，城市 n 是 Metsälä。
接下来的 m 行，每行描述一条航班，包含三个整数 a，b，和 c：表示从城市 a 到城市 b 的一条单向航班，航班的价格为 c。
你可以假设从 Syrjälä 到 Metsälä 至少有 k 条不同的路线。
输出格式
输出 k 个整数：表示从 Syrjälä 到 Metsälä 的 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
样例1解释 最便宜的三条路线分别是：
-
1→3→41 → 3 → 41→3→4（价格为 4）
-
1→2→3→41 → 2 → 3 → 41→2→3→4（价格为 4）
-
1→2→41 → 2 → 41→2→4（价格为 7）
因此，输出价格分别为 4、4 和 7。
说明/提示