这么写问题出现在取出 t 时,t 的次短路可能还没跑出来,那用这时候的 t 更新后续点的情况就不对了
比如
1->2 1
2->3 2
1->4 3
4->3 4
当你取出 3 的时候 1->4->3 还没出来,那么你再往后更新的时候这么走的路径就出不来了,如果 1->4->3 真的是 1->3 的次短路,这种走法也真的是到后边某个点的次短路,你就算不出来了
那种能走重复点的是它会在更新了次短路以后再入队,也就是说 3 的 1->4->3 这条次短路出来的时候,它会把 3 再放进去一次,而且取出来的时候因为 dis 还跟 3 的次短路相等着,所以还是有效状态,会往后再更新
所以这两种次短路不太能混用
说简单点就是可能出队时次短路还没算出来,但如果在次短路算好后再出队就会重复计算
思路来源:Darko1227
窝只是把私信弄出来,警示后人...
stO %%% Darko1227 %%% Orz
