大部分题解中,通过坐飞机更新答案后会把更新后的dis加入优先队列中。 就是这个部分:
p.push((llt){i,dis[i]});//遇到更新了最短路的点,放到队列中去
那么此时似乎无法保证这两个dis都是最小值? 比如两个点xxx,yyy被更新然后跑最短路,disxdisxdisx> disydisydisy且xxx先进入优先队列。那么disydisydisy实际上是可以更新disxdisxdisx的,然而因为x已经访问过了,那么只会更新disxdisxdisx,无法更新xxx相邻的点。
是因为这样的情况不会发生吗?虽然我模不出来但是也无法证明不会有这样的情况。求大佬解答谢谢。