WA on #9 #10

菜成狗了

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
long long int n,m,T,vis[2010],dis[2010],cnt[2010];
struct zyx{
	LL to,w;
};
vector<zyx> e[2010];
queue<LL> q;
bool spfa(){
	dis[1]=0;
	vis[1]=1;
	q.push(1);
	while(!q.empty()){
		LL u=q.front();
		q.pop();
		vis[u]=0;
		for(LL i=0;i<e[u].size();i++){
			LL v=e[u][i].to,w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)return 1;
				if(!vis[v])q.push(v),vis[v]=1;
			}
		} 
	}
	return 0;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(LL i=1;i<=m;i++){
			LL u,v,w;
			cin>>u>>v>>w;
			if(w>=0)e[u].push_back((zyx){v,w}),e[v].push_back((zyx){u,w});
			else e[u].push_back((zyx){v,w});
		}
		if(spfa())cout<<"YES\n";
		else cout<<"NO\n";		
		for(LL i=0;i<=n;i++)e[i].clear();
		memset(dis,inf,sizeof(dis));
		memset(cnt,0,sizeof(cnt));
		memset(vis,0,sizeof(vis));
		while(!q.empty())q.pop();
	}
	return 0;
}