关于此题dj
查看原帖
关于此题dj
373938
wowwowwow楼主2024/10/3 10:54

大部分题解中,通过坐飞机更新答案后会把更新后的dis加入优先队列中。 就是这个部分:

p.push((llt){i,dis[i]});//遇到更新了最短路的点,放到队列中去

那么此时似乎无法保证这两个dis都是最小值?
比如两个点xx,yy被更新然后跑最短路,disxdisx> disydisyxx先进入优先队列。那么disydisy实际上是可以更新disxdisx的,然而因为x已经访问过了,那么只会更新disxdisx,无法更新xx相邻的点。

是因为这样的情况不会发生吗?虽然我模不出来但是也无法证明不会有这样的情况。求大佬解答谢谢。

2024/10/3 10:54
加载中...