次短路的松弛条件求教
查看原帖
次短路的松弛条件求教
91681
Error_666楼主2020/5/30 17:28

一开始我是这样写的:

  • 有点x和y,用x尝试松弛y时:
    1. 如果x的最短路可以更新y的最短路,那么y的次短路就变为其最短路,其最短路更新为x的最短路+xy间距离
    2. 如果x的最短路不可以更新y的最短路却可以更新y的次短路,那么y的次短路就更新为x的最短路+xy间距离

可是这样WA了,我调错时试着要Dij里写了一句:(表示是否有点的最短路比其次短路还大的)

if(dis1[x]>dis2[x]) cout<<"QWQ\n";

结果居然输出了好多个QWQ!?

必须再加一个条件才可以AC:如果x的次短路可以更新y的次短路,那么y的次短路就更新为x的次短路+xy间距离

这是为什么呢?求大佬帮蒟蒻答疑。

不起眼的代码

2020/5/30 17:28
加载中...