@[Hzxleo4](/space/show?uid=31619) spfa理论复杂度O(nm),而当有负环的时候，bfs的spfa的复杂度就真的是理论复杂度了。。。（想象一下n个点构成了一个巨大无比的负环。。。）
by 1124828077ccj @ 2018-07-28 19:41:36
我BFS加上玄学优化过了2333
by Hono @ 2018-07-28 20:08:01
@[陈常杰](/space/show?uid=14738) 那dfs理论复杂度还是指数级别的呢。
dfs为什么能过呢？
在判负环（3385， 非本题）一题中，只有bfs能过。
by Hzxleo4 @ 2018-07-28 20:08:56
@[Hzxleo4](/space/show?uid=31619) 因为出题人一般会恶意卡bfs而忽略DFS，所以dfs判读负环就没被卡到
by moye到碗里来 @ 2018-07-28 20:20:04
@[陈常杰](/space/show?uid=14738) 那就算是O(nm)也过得去啊
by Nemlit @ 2018-08-02 08:31:44