HDU 6705 – path

题目链接：HDU 6705

题目要在无源有向带圈图中找第$k$短的路径。
比赛的时候我用堆动态维护前$50000$大的$d$（与Dijkstra中$d$意义相同），暴力拓边，以TLE告终。
实际上没有必要对所有的边进行拓展，如下图中$A$拓展到了$B$，这条边是全局最小的边，接着我们用$B$去拓展新边的时候，其实只要考虑与$B$邻接的最小的一条边，这个时候$AB+BC$被加入堆中，但是有可能$AB+BC$不是$AB$的下一个状态，因为只要比$AB$大一点点就可能是它的下一个状态，所以$AF$可能影响$AB+BC$的排名，所以也要加入堆中。

所以，综上所述，我们对每个点的出边进行排序，用堆动态维护当前最小的路径，每次BFS拓展的时候只要拓展当前点最小的出边和当前边的下一条边即可。
渐进时间复杂度$O(T(n+q)\log n)$。