带负权边的图论问题判断是否存在路径注意事项 -- inf / 2

作者：

zhengyh , 2020-03-07 17:13:45 , 所有人可见 , 阅读 811

2

1

当三角不等式的更新变量, 有负数时, 不能写成这样

if(dis[n] == inf) puts("impossible");
else cout << dis[n] << endl;

因为如果有负权边, 在三角不等式更新的时候, 会导致dis[n] < inf

写成这样提高容错率

if(dis[n] > inf / 2) puts("impossible");
else cout << dis[n] << endl;