【模板】SPFA判定负环_ETO的博客

洛谷上有模板题：负环

代码：

#include <bits/stdc++.h>
#define Max 2010
using namespace std;

int n,m,t,s;
int first[Max],cnt[Max],dis[Max],vis[Max];
struct shu{int to,next,len;};
shu edge[6010];
queue<int>q;

inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') {f=-1;c=getchar();}
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}

inline void build(int x,int y,int z)
{
	edge[++s].next=first[x];
	first[x]=s;
	edge[s].to=y;
	edge[s].len=z;
}

inline int SPFA()
{
	while(!q.empty()) q.pop();
	dis[1] = 0,cnt[1] = 1;
	q.push(1);
	while(!q.empty())
	{
	  int point = q.front();
	  q.pop();
	  vis[point] = 0;
	  for(register int u=first[point];u;u=edge[u].next)
	  {
		int to=edge[u].to;
		if(dis[to] > dis[point] + edge[u].len)
		{
		  dis[to] = dis[point] + edge[u].len;
		  if(!vis[to])
		  {
		  	cnt[to] = cnt[to] + 1;
		    if(cnt[to] >= n) return 1; 
			vis[to] = 1;
			q.push(to);
		  }
		}
	  }
	}
	return 0;
}

int main()
{
	t=get_int();
	while(t--)
	{
	  s=0;
	  n=get_int(),m=get_int();
	  for(register int i=1;i<=n;++i) vis[i] = cnt[i] = first[i] = 0,dis[i] = 1e9;
	  for(register int i=1;i<=m;++i)
	  {
	    int x=get_int(),y=get_int(),z=get_int();
	    build(x,y,z);
	    if(z >= 0) build(y,x,z);
	  }
	  SPFA() ? printf("YE5\n") : printf("N0\n");
	}
}#include <bits/stdc++.h>
#de