[Acwing] 368. 银河 spfa_Dfs优化+差分约束

前言

传送门 :

思路

首先这题肯定是 差分约束 同时 需要 s p f a spfa spfa判断负环

但是我们都知道, S p f a Spfa Spfa的时间复杂度最坏是 O ( n ∗ m ) O (n*m) O(n∗m)的,

所以这题会使用 S C C SCC SCC进行考虑

但是我还是不信邪,所以通过使用 栈优化 很好的 T L E TLE TLE了

然后我瞄了一眼题解,发现有栈优化过的,但是有一个更离谱的,一开始我以为他只是队列优化+快读

结果看了他的运行效率 148 m s ! ! 148ms!! 148ms!!,惊呆了

仔细发现,这位大佬的代码使用的是 s p f a spfa spfa的 D f s Dfs Dfs优化,该优化可以使得判断环的时候,时间复杂度将为 O ( m ) O(m) O(m)

[另一个大佬的spfa各种优化链接] [Acwing大佬的 Dfs优化代码]

Code

int to[maxn