关于本题求k短路的错解
查看原帖
关于本题求k短路的错解
369291
winter2020楼主2022/6/22 16:32

这么写问题出现在取出 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

2022/6/22 16:32
加载中...