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\n");

		else

			printf("N0\n");

	}

	return 0;

}
巴特西

spfa_dfs找负环

最新文章

热门文章
