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)$。

 

说点什么

avatar
50
  Subscribe  
提醒