K 次最短路

【题目描述】

给定一个不一定是简单的有向图，图中有 $N$ 个顶点和 $M$ 条边。第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$，权值为 $c_i$。

对于 $i$ 从 $1$ 到 $K$（包括 $K$），输出从顶点 $s$ 到顶点 $t$ 的第 $i$ 短的游走的长度 $x_i$。如果不存在这样的游走，则输出 -1。

长度相同的多条游走视为不同的游走。

【输入】

$N~M~s~t~K$
$u_0~v_0~c_0$
$u_1~v_1~c_1$
$u_2~v_2~c_2$
:
$u_{M-1}~v_{M-1}~c_{M-1}$

【输出】

$x_1$
$x_2$
$\vdots$
$x_K$

【输入样例】

4 5 0 3 5
0 1 1
1 2 1
2 3 1
0 2 1
1 3 1

【输出样例】

2
2
3
-1
-1

【数据范围】

• $1 \leq N, M \leq 300000$
• $1 \leq K \leq 300000$
• $0 \leq s, t < N$
• $0 \leq u_i, v_i < N$
• $0 \leq c_i \leq 10000000$

【来源】

Library Checker（yosupo06） k_shortest_walk