一开始我是这样写的:
- 有点x和y,用x尝试松弛y时:
- 如果x的最短路可以更新y的最短路,那么y的次短路就变为其最短路,其最短路更新为x的最短路+xy间距离
- 如果x的最短路不可以更新y的最短路却可以更新y的次短路,那么y的次短路就更新为x的最短路+xy间距离
可是这样WA了,我调错时试着要Dij里写了一句:(表示是否有点的最短路比其次短路还大的)
if(dis1[x]>dis2[x]) cout<<"QWQ\n";
结果居然输出了好多个QWQ!?
必须再加一个条件才可以AC:如果x的次短路可以更新y的次短路,那么y的次短路就更新为x的次短路+xy间距离
这是为什么呢?求大佬帮蒟蒻答疑。
不起眼的代码