属实。
在非负边权的图中，随手卡 SPFA 已是业界常识。在负边权的图中，不把 SPFA 卡到最慢就设定时限是非常不负责任的行为，而卡到最慢就意味着 SPFA 和传统 Bellman Ford 算法的时间效率类似，而后者的实现难度远低于前者。
SPFA 的受到怀疑和最终消亡，是 OI 界水平普遍提高、命题规范完善和出题人的使命感和责任心增强的最好见证。
Update：
为了激励并推广卡 SPFA 这一行为，我提供一种最简单的卡 SPFA 的方法（同时适用于有向图和无向图）：
Step 1 生成一棵以起点为根的树，树高尽量高（比如 1 为起点时，可以令每个点 i 的父亲在 max(i-5,1) 到 i-1 随机），边权随机，作为最短路径树，同时直接递推求出每个点的带权深度 d(i)
Step 2 对于剩下的边，端点 (a, b) 随机，边权在 |d(b)-d(a)| 到 |d(b)-d(a)|+5 随机（如果是有向图则去掉绝对值符号，5 可以换成其他较小的正数）
这样生成的图中，次短路的条数非常的多，而 SPFA 一旦错误地进入了次短路的分支，就会使得一整棵子树被赋错误的距离，从而在后期不得不重新更新。而由于边权接近，剪枝的效果会受到很大影响。
这个生成方法代码简单易写，只需要大量的随机，不需要构造网格等特殊结构，生成器中甚至不需要建图 ，适合所有有责任心的出题人使用。 |
|
转播
