第 K 短路（K-Shortest Walk）

问题描述

给你一个含 $N$ 个顶点、$M$ 条边的有向图（不一定简单），第 $i$ 条边从 $a_i$ 指向 $b_i$，权重为 $c_i$。
给定起点 $s$ 和终点 $t$，对 $i = 1, 2, \dots, K$（包含），请输出第 $i$ 短的路径长度（即按非降序排列的第 $i$ 小的路径权值和）；若第 $i$ 短路径不存在，输出 -1。

注：题目中使用 “walk” 而非 “path”，且说明“Multiple walks with the same length are considered different walks”，但输出仅要求长度；结合约束与常见题意，此处“walk” 允许重复经过顶点/边，但输出的是长度值，相同长度的不同 walk 视为不同 walk，但若第 $i$ 个最小长度不存在（如总路径数 < $i$），则输出 -1。

约束条件

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq M \leq 3 \times 10^5$
• $1 \leq K \leq 3 \times 10^5$
• $0 \leq s, t < N$
• $0 \leq a_i, b_i < N$
• $0 \leq c_i \leq 10^7$

输入格式

$N\ M\ s\ t\ K$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
:
$a_{M-1}\ b_{M-1}\ c_{M-1}$

输出格式

$x_1$
$x_2$
:
$x_K$

其中 $x_i$ 为第 $i$ 短 walk 的长度（若不存在则为 -1）。

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