VioletIsMyLove @ 2023-05-11 21:29:23
if(!vis[son[i]]&&dis[a.id]+v[i]<dis[son[i]]){
dis[son[i]]=dis[a.id]+v[i];
put(dis[son[i]],son[i]);
} if(dis[a.id]+v[i]<dis[son[i]]){
dis[son[i]]=dis[a.id]+v[i];
if(vis[son[i]])put(dis[son[i]],son[i]);
}按着前者这么写也能通过这道题，但是能证明前者的正确性吗>_<，感觉这样会有些值更新不到
by VioletIsMyLove @ 2023-05-11 21:30:32
还是说就是纯纯数据太弱了才把第一种写法放过去了>_<
by Rainybunny @ 2023-05-11 21:37:56
vis 为 true 的结点的 dis 已经被更新为全局最短路了, 绝对无法再被松弛, 所以前一种也是对的.
by Happy_Orca @ 2023-05-11 21:42:44
@VioletIsMyLove dij的贪心保证之前遍历过的节点是最小值了
by VioletIsMyLove @ 2023-05-11 21:44:05
@Rainybunny 明白了，谢谢>_<
by VioletIsMyLove @ 2023-05-11 21:44:32
@fo_ol 感谢！！