（叠甲）我可能记错了。
不加inq优化的话spfa的复杂度上界也是O(nm)的，n是点数，m是边数
by scp020 @ 2024-02-03 15:44:35
事实上 SPFA 是 Bellman-Ford 的队列优化的圈内别名，之所以 Bellman-Ford 算法是 $O(nm)$ 的，不是因为发明人太菜了，是因为本来也不能轻而易举地降低复杂度的级别，“SPFA” 这个名字就是个闹剧，死了理所应当。
说回这题，去掉 `vis` 记号只是可能会花时间更多一点，你用朴素的 Bellman-Ford 写也能过就是了。
by Terrible @ 2024-02-03 15:51:29
@[scp020](/user/553625) 应该是这样的，最多退化回Ballman-Ford
（叠甲）我也可能记错了。
by 幻想繁星 @ 2024-02-03 15:51:49
@[幻想繁星](/user/649095)
@[Terrible](/user/195942)
@[scp020](/user/553625)
请问大佬，inq优化有用吗？作用大不大？我用了之后感觉差不多。
另：单源最短路径【弱化版】我的spfa用了200+ms正常吗？ (ygpt祭）
by litjohn @ 2024-03-19 22:09:11
@[litjohn](/user/537934) 多数情况下有用，极端数据可以退化到bellman ford的复杂度
by scp020 @ 2024-03-19 22:11:06
就目的性而言，“优化”的核心意涵是指存在特殊情况使得花销相较原版更优。优化代码在某种情况下几乎没有提升，甚至消耗增加是正常现象。
by Terrible @ 2024-03-19 22:29:23