题目大意

给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。
有输出YE5，否则输出N0（我没打错字）

思路

显然spfa判断负环的水题
code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int head[2001],d[2001],n,m,k,tot=1;
queue<int> q;
struct f{
    int to,next,w;
} b[10001];
bool book[2001];
void add(int x,int y,int z)
{
    b[tot].to=y;
    b[tot].w=z;
    b[tot].next=head[x];
    head[x]=tot;
    tot++;
}
int ans[2001];
bool vis[2001];
void spfa(int x)
{
    q.push(x);
    for (int i=1;i<=n;i++)
    {
    	d[i]=2000*1000+20;
    	vis[i]=0;
    	ans[i]=0;
	}
	vis[x]=1;
	d[x]=0;
    while (q.size())
    {
    	int xx=q.front();
    	q.pop();
    	vis[xx]=0;
    	for (int i=head[xx];i;i=b[i].next)
    	{
    		if (d[b[i].to]>d[xx]+b[i].w)
    		{
    			d[b[i].to]=d[xx]+b[i].w;
    			if (vis[b[i].to]==0)
    			{
	    			vis[b[i].to]=1;
	    			ans[b[i].to]++;
		    		if (ans[b[i].to]>=n)
					{
						cout<<"YE5"<<endl;
						return;
					}
    				q.push(b[i].to);
				}
			}
		}
	}
	cout<<"N0"<<endl;
	return;
}
int main()
{
	int t;
	cin>>t;
	while (t--)
	{
		memset(head,0,sizeof(head));
	    cin>>n>>m;
	    tot=1;
	    for (int i=0;i<m;i++)
	    {
	        int x,y,z;
	        cin>>x>>y>>z;
	        if (z>=0) add(x,y,z),add(y,x,z);
	        else add(x,y,z);
	    }
	    spfa(1);
	}
	return 0;
}