在文章《如何优化SPFA》发表评论：

@_sapnap_dream_ 哪里被HACK了

在文章《如何优化SPFA》发表评论：

P3275的AC记录：https://www.luogu.com.cn/record/261118532

在文章《如何优化SPFA》发表评论：

check里有一个小bug，如果m特别小，就会不停跑check()，导致TLE。关于我是怎么发现的：https://www.luogu.com.cn/record/261113990

在文章《如何优化SPFA》发表评论：

在本地运行SPFA时要把快读去掉；有SPFA求最长路版本。

**前置芝士**：SPFA是 Bellman-Ford 算法的优化。but，它的最坏时间复杂度为 $O(nm)$，且总被某些不愿意透露姓名的~~邪恶~~善良出题入卡没（网格图、菊花图等数据）。 众所~~不~~周知 SPFA 优化主要是双端队列实现的STL、LLL优化，使其接近 Dijkstra 的优先队列。这样做完全丢…

第一版： ```cpp #include using namespace std; const int N=1e6+8,M=2e6+8,C=0x3f3f3f3f; struct G{int x,u,t;} a[M sta; memset(ans,C,sizeof(ans)); memset(w,0,sizeof(w))…

在讨论《是否有带负权的单源最短路模板》回复：

@[CR400BF_1145](luogu://user/1029340) [Link](https://www.luogu.com.cn/problem/T647765) 自己出的，数据是对的

在文章《CTT2025 游记：好想成为人类啊》发表评论：

qp

```cpp #include using namespace std; const int N=505,M=5e4+8; struct G{int x,t;} a[M]; int n,m,e,w[N],h[N],cnt=0,k[N]; bool dfs(int x){ w[x]=1; for (int i=h[x],…

[书接上回](https://www.luogu.me/article/nlvjxj6a) ```cpp #include using namespace std; #define ll long long #define getchar_fread() (p1==p2&&(p2=(p1=buf)+fread(buf,…

在文章《题解：AT_abc265_g [ABC265G] 012 Inversion》发表评论：

这不就暴力吗？

# ~呜呜呜，我的SPFA又si了~ 在[spfa优化到AC](https://www.luogu.me/article/1rd2qxvn)中， 坏消息：Dep优化属于补救性优化，轻轻一卡就卡掉了，只需要让源点与每个节点连一条边权特别大的边，优化就会失效，就会退化为DFS-spfa（假算法）或普通SPFA加logn常数…

在讨论《关于SPFA》回复：

@[linhanmo](luogu://user/1492046) 是，但不全是

在讨论《关于SPFA》回复：

还有你是在本地测的吗？

在讨论《关于SPFA》回复：

@[BNCDBD](luogu://user/1357674) 标程可否给我看看

在讨论《关于SPFA》回复：

@[BNCDBD](luogu://user/1357674) SPFA如果不被卡不本来就比Dij要快吗？

在讨论《关于SPFA》回复：

@[IcyDragon](luogu://user/1178907) DS给的hack数据太水了，普通SPFA都卡不了

在讨论《关于SPFA》回复：

@[IcyDragon](luogu://user/1178907) 哟，好基友来啦 你去问一下就知道了 code: ```cpp #include using namespace std; #define ll long long const int MAXN=1 other.dep;} }; int p[N],de…

在讨论《关于SPFA》回复：

菊花和网格根本卡不了

在讨论《关于SPFA》回复：

@[nbhs23a28](luogu://user/1271868) 了解过了

前言： 如果没看过[https://www.luogu.com.cn/discuss/1126463](https://www.luogu.com.cn/discuss/1126463)，可以先看看 书接上回，我发明了一个SPFA的优化，并且通过了Luogu的[【模板】单源最短路径（标准版）](https://www.…

在讨论《关于SPFA》回复：

个人感觉求强联通那个tarjan也可以判负环（如果不需要求最短路的话

```cpp #include using namespace std; #define ll long long #define int long long #define qwq (data.s+=a[u].x,data.s%=m,data.mx=max(data.mx,a[u].x),data.mn=min(da…

### 时间复杂度：$o(n·logm) \to o(n·logn+m)$ ```cpp #include using namespace std; #define ll long long const int MAXN=1 inline void read(T &x){ x=0; T c=getchar_fread(…

在讨论《帮宣超快SPFA!!!比Dij还快!!!》回复：

@[Brute_Force](luogu://user/995899)可以了，但是在Dev里运行的很慢（可能是因为递归层数太大了），这种情况直接把bfs和tarjan的调用注释掉即可。

在讨论《帮宣超快SPFA!!!比Dij还快!!!》回复：

我好像找到原因了。 ```cpp #include using namespace std; int find(int x){ if(x>45000) return 1; return find(x+1); } signed main(){ cout <<find(1); return 0; } ``` 在Dev-C+…

在讨论《帮宣超快SPFA!!!比Dij还快!!!》回复：

@[modongtao](luogu://user/638073) 不是TLE，是RE

在讨论《帮宣超快SPFA!!!比Dij还快!!!》回复：

唉，我已经尽力了。关于tarjan，它已经洗了！

在讨论《帮宣超快SPFA!!!比Dij还快!!!》回复：

@[CarroT1212](luogu://user/319803) 你貌似不是卡掉了我的SPFA，而是卡掉了我的tarjan

在讨论《帮宣超快SPFA!!!比Dij还快!!!》回复：

@[CarroT1212](luogu://user/319803) 好，我再改改