不知道为什么都说第K短路的A*算法是假的。
不过多知道一种比较广泛的方法也好。
整理留坑

其实很多题都有类似的思路，就是把所有可能的情况构造成一颗大根树（父亲比儿子优秀），在已解锁区域内选出一个当前最优值，然后解锁他的儿子们。（这些优化思路在网络流中也能用到……）

时间复杂度O((n+m)log(n+m)+Klog(mK))O((n+m)log(n+m)+Klog(mK))
空间复杂度O((nlogm+Klogm)O((nlogm+Klogm)
(n为点数，m为边数）
前置技能：可持久化可并堆（注意不要多套一层主席树）

还是先对终点求一遍最短路树，令终点为根。
第K短路可以写成走若干条树边和非树边交替。
现在定义非树边i->j的新权值为(经过这条边的做短路长度-全局最短路长度)
即v[i][j]+dis[j][T]−dis[i][T]v[i][j]+dis[j][T]-dis[i][T](其中v表示原边权，dis表示两点间最短路,T表示终点）

考虑第二短路。
显然是经过【从起点到终点最短路上连出去非树边新权值最小的那条边】的最短路。
(反正总会有一个点不属于当前最短路)
考虑第三短路。
发现第三短路也可能从第二短路基础上修改一条边得到，所以第二短路上的非树边权值也要统计进来。（当然还要加上偏移量）
可以看作每次求次短路就是清掉当前最短路，并把当前最短路可以通过该边某条边得到的其他路径加入考虑集合。

如此循环，会发现每次求一遍次短路径的过程其实是这样的：
找新权值最小的边->统计答案并弹出该边->将【这条边到根路径上的非树边】加上偏移量加入候选集合。
求K-1遍，结束。
用可并堆动态插入集合并动态维护最小值，复杂度就下来了。

要注意的是一条边可能会被不同的到起点的路径弹出（一个集合会被加入多次），所以如果用可并堆维护这个点到根路径上的非树边是不可能的，需要使用可持久化可并堆实现插入集合。

预处理的时候同样是直接最短路树上可持久化可并堆，这里因为只有O(m-n)条边会被添加，所以初始化时间复杂度只有O((m-n)log(m-n))
在求解的时候每次并入集合会带来O(logm)的空间消耗，但是在堆中看上去是增加了O(m)条边，所以会有顶上的时空复杂度。