难度估计：CF 3100～3300

题目描述

给定一个带正权的有向图，其中一个顶点为源点 $s$，另一个顶点为终点 $t$。

先求从 $s$ 到 $t$ 的最短路径，然后求第二短路径，即除第一条路径之外最短的一条；再求第三短路径，以此类推。请输出前 $k$ 条路径的长度。

这里的“路径”允许重复经过顶点或边，因此实际上求的是前 $k$ 短的 walk。不同路径可以具有相同的长度。

输入格式

第一行包含三个整数 $n,m,k$：

• $2\le n\le 10000$；
• $2\le m\le 50000$；
• $2\le k\le 10000$。

第二行包含两个整数 $s,t$，满足 $1\le s,t\le n$ 且 $s\ne t$。

接下来 $m$ 行，每行包含三个整数 $a,b,c$，表示一条从 $a$ 到 $b$、长度为 $c$ 的有向边：

• $1\le a,b\le n$，$a\ne b$；
• $1\le c\le 1000$。

同一对顶点之间可以存在多条平行边。

输出格式

输出 $k$ 行，按非降序给出前 $k$ 条从 $s$ 到 $t$ 的路径长度。

如果实际存在的路径数量不足 $k$ 条，则对每一条不存在的路径输出：

NO

样例 1

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

2
2
3
NO
NO

样例 2

4 4 5
1 4
1 2 10
2 3 10
3 4 10
3 2 10

30
50
70
90
110

样例 3

2 2 10
1 2
1 2 5
2 1 7

5
17
29
41
53
65
77
89
101
113

算法要点

使用 Eppstein 的 $k$ 短路算法。

先在反图上从 $t$ 做 Dijkstra，得到每个点到 $t$ 的最短距离 $d[u]$，并选出一棵指向 $t$ 的最短路树。对于任意非树边 $u\to v$，定义其偏离代价：

$\Delta=w(u,v)+d[v]-d[u]\ge 0$。

一条 $s\to t$ 路径可以表示为“最短路树路径 + 若干条 sidetrack 边”，其长度等于 $d[s]$ 加上所有 sidetrack 的 $\Delta$ 之和。

对每个顶点维护从该点沿最短路树到 $t$ 的路径上可以选择的 sidetrack，并用可持久化可合并堆组织。随后使用全局优先队列按照附加代价从小到大枚举候选状态，即可依次得到前 $k$ 短路径。

复杂度约为 $O((n+m)\log n+k\log k)$。