spfa板子

判负环，求带负权边的最短路。

#include<stdio.h>
#include<vector>
#include<queue>
#include<cstring>
const int inf=0x3f3f3f3f;
using namespace std;
struct node{
   
	int a,b;
	node(int _a,int _b):a(_a),b(_b){
   
	}
};
vector<node> v[1000];
int n,d[1000],m,w,num[1000];
bool vis[1000];
bool spfa(){
   
	queue<int> q;
	q.push(1);
	vis[1]=true;
	num[1]++;
	d[1]=0;
	while(!q.empty()){
   
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int j=0;j<v[u].size();j++){
   
			int t=v[u][j].a;
			int tt=v[u][j].b;
			if(d[u]+tt<d[t]){
   
				d[t]=d[u]+tt;
				if(!vis[t])
				q.push(t);
				vis[t]=true;
				num[t]++;
				if(num[t]>=n)	return true;
			}
		}
	}
	return false;
}
void init(){
   
	for(int i=0;i<1000;i++)
		v[i].clear();
	memset(num,0,sizeof(num));
	memset(vis,0,sizeof(vis));
	fill(d,d+1000,inf);
}
int main(){
   
	int t;
	scanf("%d",&t);
	while(t--){
   
		init();
		scanf("%d%d%d",&n,&m,&w);
		for(int i=0;i<m;i++){
   
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			v[x].push_back(node(y,z));
			v[y].push_back(node(x,z));
		}
		for(int i=0;i<w;i++){
   
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			v[x].push_back(node(y,-z));
		}
		if(spfa())	printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}