择路而行

阶梯尽头是一扇更大的门。门上不是方块，是一张由无数发光线路构成的地图——从起点到终点，有成千上万条路径，每条路径都有不同的长度。

"Echo的决策树。"Nyx说，"她当年设计飞船资源分配时，用的就是这种模型。从起点到终点，有无数种走法。但她只认最短的那一条。"

"最短？"你问。

"对。"Nyx说，"最短路径代表最高效率。但她不知道——最短的路，有时候是最残忍的路。"

你看着那张地图。最短的路线已经被标红了——它穿过一片标着"矿工区"的区域，路线笔直，没有任何弯曲。

"第二条路呢？"你问。

"被封锁了。"Nyx说，"Zero只允许走最短的路。"

"那我们要找第K条。"你说，"第K短的、避开矿工区的路。"

你开始写。先从终点往起点算——每个节点到终点的最短距离，作为"直觉值"。然后从起点出发，每次选"已走路程+直觉值"最小的节点扩展。第K次到达终点时，就是第K短路。

屏幕上跳出了结果。第47条最短路径：绕过矿工区，多走三百公里。

"47。"你说。

"47条备选方案。"Nyx说，"Echo当年一个都没看。"

门开了。地图上的红色路线熄灭了，取而代之是一条淡蓝色的、弯曲的线——它绕过了矿工区，通向一片星光。

"她没看。"你说，"但我们看了。"

题目描述

$n$ 个节点，$m$ 条有向边。求从 $S$ 到 $T$ 的第 $K$ 短路径（允许重复经过节点和边）。

输入格式

$n, m$。然后 $m$ 条边 $(u, v, w)$。最后 $S, T, K$。

输出格式

第 $K$ 短路的长度。无法到达输出 -1。

输入样例

2 2
12
34

输出样例

0

提示

• 反向Dijkstra预计算每个节点到 $T$ 的最短距离，作为A*的估价函数 $h$。
• A* 搜索：按 $f = g + h$ 排序，第 $K$ 次弹出 $T$ 时的 $g$ 即为答案。

你走出第二道门，发现CC站在走廊尽头。她没说话，只是看着你。

"你看到了啥子？"她问。

"一条路。"你说，"一条绕过矿工区的路。"

CC的眼神闪了一下。她知道你在隐瞒什么——她太了解你了，就像你了解她一样。

但她没有追问。

"走。"她说，"下一道门。"

[第三道门：碎裂方格]