求助,关于建立超级源点跑SPFA求最大解的疑问
查看原帖
求助,关于建立超级源点跑SPFA求最大解的疑问
38778
A13579楼主2025/6/30 16:03

这题用节点1跑最短路求最大解是正确的,但建立超级源点0跑最短路所求出的最大解却不对。

对于样例
4 2 1
1 3 10
2 4 20
2 3 3
SPFA(1)得到的最短路从1到n为 0 7 10 27
而SPFA(0)得到的最短路从1到n为 -3 -3 0 0
SPFA(0)得到的像是最小解. 同样是求解最短路,两者得到的解却不同, 这是为什么

2025/6/30 16:03
加载中...