AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
int tot,head[501000],vis[10100],dis[10100],cnt[10010];
queue<int> q;
struct node{
	int v,w,nxt;
}a[501000];
void add(int u,int v,int w)
{
	a[++tot].v=v;
	a[tot].w=w;
	a[tot].nxt=head[u];
	head[u]=tot;
}
int spfa(int s)
{
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(int i=head[t];i;i=a[i].nxt)
		{
			int v=a[i].v,w=a[i].w;
			
			if(dis[v]>dis[t]+w)
			{
				dis[v]=dis[t]+w;
				
				if(vis[v]==0)
				{
					cnt[v]++;
					if(cnt[v]>n)
					{
						return 1;
					}
					q.push(v);
					vis[v]=1;
				}
			
			}
		}
	}
	return 0;
}
int main(){
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		memset(head,0,sizeof(head));
		memset(a,0,sizeof(a));
		memset(cnt,0,sizeof(cnt));
		tot=0;
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			if(w>=0)
			{
				add(v,u,w);
			}
			add(u,v,w);
		}
		
		if(spfa(1)==1) 
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	
	return 0;
}

spfa这里

if(vis[v]==0)
{
    cnt[v]++;
    if(cnt[v]>n)
 	{
      return 1;
    }
     q.push(v);
     vis[v]=1;
}
为什么cnt[v]++;一定要写到if(vis[v]==0)里面