链接: https://cses.fi/problemset/task/1195

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务是找出从 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$ 条最便宜路线的价格。

数据范围

$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$

样例输入

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 \rightarrow 3 \rightarrow 4$（价格 $4$）、$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$（价格 $4$）和 $1 \rightarrow 2 \rightarrow 4$（价格 $7$）。