spfa_dfs找负环

luogu

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
inline void in(int &p,char c=getchar(),bool f=0)
{
	while((c<'0' or c>'9') and c!='-')
		c=getchar();
	p=0;
	if(c=='-')
		f=1,c=getchar();
	while(c>='0' and c<='9')
		p=(p<<3)+(p<<1)+c-'0',c=getchar();
	if(f)
		p=-p;
}
int n,m;
struct way
{
	int to;
	int cost;
};
vector <way> v[200001];
bool fuhuan,vis[200001];
long long dis[200001];
void spfa_dfs(int x)
{
	vis[x]=1;
	for(unsigned int i=0;i<v[x].size();i++)
	{
		if(dis[x]+v[x][i].cost<dis[v[x][i].to])
		{
			dis[v[x][i].to]=dis[x]+v[x][i].cost;
			if(vis[v[x][i].to])
			{
				fuhuan=1;
				//vis[x]=0;
				return ;
			}
			spfa_dfs(v[x][i].to);
		}
	}
	vis[x]=0;
}
int main()
{
	//freopen("shuru.txt","r",stdin);
	int t;
	in(t);
	while(t--)
	{
		in(n);in(m);
		for(int i=1;i<=n;i++)
			v[i].clear();
		memset(vis,0,sizeof(vis));
		memset(dis,0,sizeof(dis));
		fuhuan=0;
		for(int i=0;i<m;i++)
		{
			int x,y,c;
			in(x);in(y);in(c);
			way a;
			a=(way){y,c};
			v[x].push_back(a);
			if(c>=0)
			{
				a.to=x;
				v[y].push_back(a);
			}
		}
		for(int i=1;i<=n;i++)
			if(!fuhuan)
				spfa_dfs(i);
		if(fuhuan)
			printf("YE5
");
		else
			printf("N0
");
	}
	return 0;
}