$SPFA$ 被卡成 $O(nm)$ 的情况不是完全图吗（如果我没记错的话
by 月落落落 @ 2021-10-09 10:42:41
@[泷泽三月](/user/115936) ？
卡 SPFA 不需要完全图啊
by djwj233 @ 2021-10-09 10:45:47
@[泷泽三月](/user/115936) 用网格图套一个菊花能卡掉大多数写法的 SPFA 吧
by djwj233 @ 2021-10-09 10:47:42
楼上正解
by 初雪_matt @ 2021-10-09 11:01:00
@[djwj233](/user/114558) $n^2$卡卡常能过吧？)不过时间复杂度似乎不正确
by 初雪_matt @ 2021-10-09 11:02:36
@[初雪_matt](/user/360083) 就是在问有没有复杂度正确的解法（
by djwj233 @ 2021-10-09 11:13:52
@[djwj233](/user/114558) 好像没有了，加dijkstra堆优化也会被卡,某p!=np肯定也会被卡，~~就没有算法了~~
by 初雪_matt @ 2021-10-09 11:21:43
@[初雪_matt](/user/360083) 那这题不就是个假题
by djwj233 @ 2021-10-09 11:22:44
@[djwj233](/user/114558) 我太菜了，不知道
by 初雪_matt @ 2021-10-09 11:23:27
@[djwj233](/user/114558) 朴素dijkstra+优化应该能过
by 初雪_matt @ 2021-10-09 11:25:18