Description：

给一个有向带权图，求起点到终点的第 $k$ 短路。

$1\leqslant n\leqslant 5000,1\leqslant m\leqslant 200000$

Solution：

首先显然有 $A^*$ 做法，但是那个做法的复杂度是错的。

我们考虑一个经典的求第 $k$ 大值的方法，就是用一个堆，每次取出最小的，然后把所有他能扩展出的稍微差一些的放进堆里，这样重复 $k$ 次就行了，我们先建出从 $t$ 开始的最短路树，那么我们可以把每条从 $S$ 到 $T$ 的路径都拆成一些在树上的边和不在树上的边，设 $\Delta_i=dis[e[i].to]-dis[e[i].fr]-e[i].val$ ，显然在树上的边 $\Delta$ 都为 $0$ ，显然某条路径的长度就等于 $dis(s,t)+\sum\Delta$ ，然后我们的问题就转化成了选出第 $k$ 大的边的子集，那么我们就可以在最开始把所有的边都放进去，然后每次拿出一个边的集合，找到这个边的集合的末尾，然后在最短路树上查询一个以他或者他的祖先为起点的一条非树边，设 $g(v)$ 为以 $v\to t$ 这条树链上的点出发的非树边的 $\Delta$ 最小值，那么对于当前拿出来的这条树链，设最后一条边为 $e$ ，最后一条边的终点为 $v$ ，倒数第二条边的终点为 $u$ ，那么就把 $g(u)$ 中 $e$ 的下一条边替换 $e$ 生成的边集和 $g(v)$ 中最小的边放在最后生成的边集放进堆里继续操作即可。

但是显然可以发现 $g(v)$ 和 $g(fa[v])$ 有大量是相同的，因此可以用可持久化的左偏树来维护 $g(v)$ ，时间复杂度就被优化到了有理有据的 $O(n\log n+m\log m+k\log k)$ 。

Code：