之前用dfs_spfa直接跑的全挂啦！更新的数据好可怕啊！
【模板】负环
时空限制 $ quad $ 2000ms / 128MB
题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
输入输出格式
输入格式
第一行一个正整数 $ T $ 表示数据组数，对于每组数据：
第一行两个正整数 $ N M $ ，表示图有 $ N $ 个顶点， $ M $ 条边
接下来 $ M $ 行，每行三个整数 $ a,b,w $ ，表示 $ a->b $ 有一条权值为 $ w $ 的边（若 $ w<0 $ 则为单向，否则双向）
输出格式
共 $ T $ 行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。
输入输出样例
输入样例#1
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出样例#1
N0
YE5
说明
$ n le 2000 (
) m le 3000 (
) -10000 le w le 10000 (
) T le 10 $
建议复制输出格式中的字符串。 本题数据感谢@negiizhao的精心构造，请不要使用玄学算法 本题数据有更新
题解
-
记录每个点的最短路径包含的边数，超过 $ n $ 说明有负环
-
也可以卡内存、卡时间、爆了队列就判定有负环（雾 -
以及使用栈板本、 $ DFS $ 版本栈的没写过，dfs_spfa卡时间其实也能过
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
#define maxn 2005
#define maxm 3005
vector<int>E[maxn],W[maxn];
int t,n,m,dis[maxn],cnt[maxn];
bool vis[maxn];
bool spfa(){
memset(vis,0,sizeof(bool)*(n+1));
memset(dis,0x7f,sizeof(int)*(n+1));
memset(cnt,0,sizeof(int)*(n+1));
queue<int>q;
q.push(1); dis[1]=0; vis[1]=1;
while(!q.empty()){
int u=q.front(); q.pop(); vis[u]=0;
for(int i=0;i<E[u].size();++i){
int v=E[u][i],w=W[u][i];
if(dis[v]>dis[u]+w){
cnt[v]=cnt[u]+1; if(cnt[v]>=n) return 0;
dis[v]=dis[u]+w;
if(!vis[v]){ vis[v]=1; q.push(v); }
} else if(dis[v]==dis[u]+w&&w>0){
//当dis[v]=dis[u]+w时，通过u点也能在相同距离走到v点，所以路径数直接累加
cnt[v]+=cnt[u]; if(cnt[v]>=n) return 0;
dis[v]=dis[u]+w;
if(!vis[v]){ vis[v]=1; q.push(v); }
}
}
}
return 1;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){ E[i].clear(); W[i].clear(); }
for(int u,v,w,i=1;i<=m;++i){
scanf("%d %d %d",&u,&v,&w);
E[u].push_back(v);
W[u].push_back(w);
if(w>=0) {
E[v].push_back(u);
W[v].push_back(w);
}
}
if(spfa()) puts("N0");
else puts("YE5");
}
return 0;
}