POJ 3259 Wormholes(spfa判负环)

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 505
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
	int to,w,next;
	bool operator < (const Node &a) const{
		return a.w < w;
	}
}Edge[maxn * maxn];
int head[maxn * maxn],num;
int dist[maxn];
bool vis[maxn];
int T,n,m,k;

void init(){
	memset(head,-1,sizeof(head));
	num = 0;
}

void add(int u,int v,int w){
	Edge[num].w = w;
	Edge[num].to = v;
	Edge[num].next = head[u];
	head[u] = num ++;
}

bool spfa(){
	int cnt[maxn];
	memset(cnt,0,sizeof(cnt));
	memset(dist,inf,sizeof(dist));
	memset(vis,false,sizeof(vis));
	dist[1] = 0;
	cnt[1] = 1;
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i=head[u];i!=-1;i=Edge[i].next){
			int v = Edge[i].to;
			if(dist[v] > dist[u] + Edge[i].w){
				dist[v] = dist[u] + Edge[i].w;
				if(vis[v] == false){
					cnt[v]++;
					q.push(v);
					vis[v] = true;
					if(cnt[v] >= n){
						return true;
					}
				}
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d",&T);
	while(T--){
		init();
		scanf("%d%d%d",&n,&m,&k);
		for(int i=0;i<m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u, v, w);
			add(v, u, w);
		}
		for(int i=0;i<k;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u, v, -w);
		}
		if(spfa()){
			puts("YES");
		}
		else{
			puts("NO");
		}
	}
	return 0;
}