#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define M 5205 //ac
//#define M 3000 runtime error
//#define M 5000 wrong answer
#define N 505

struct node {
	int p,next,dis;
} g[M];
int n,m,w,cnt[N],inq[N],head[N],dis[N],k;

void addEdge(int s,int d,int dist) {
	g[k].p=d;
	g[k].dis=dist;
	g[k].next=head[s];
	head[s]=k++;
}
bool spfa(int s) {
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(inq,0,sizeof(inq));
	memset(cnt,0,sizeof(cnt));
	queue<int> q;
	q.push(s);
	cnt[s]=1;
	inq[s]=1;
	while(!q.empty()) {
		int t=q.front();
		q.pop();
		inq[t]=0;
		for(int i=head[t],p; i!=-1; i=g[i].next) {
			p=g[i].p;
			if(dis[p]>dis[t]+g[i].dis) {
				dis[p]=dis[t]+g[i].dis;
				if(!inq[p]) {
					q.push(p);
					inq[p]=1;
					if(++cnt[p]>n)
						return true;
				}
			}
		}
	}
	return false;
}
int main() {
	freopen("in.txt","r",stdin);
	int f;
	cin>>f;
	while(f--) {
		cin>>n>>m>>w;
		memset(head,-1,sizeof(head));
		k=0;
		for(int i=0,a,b,d; i<m; i++) {
			scanf("%d%d%d",&a,&b,&d);
			addEdge(a,b,d);
			addEdge(b,a,d);
		}
		for(int i=0,a,b,d; i<w; i++) {
			scanf("%d%d%d",&a,&b,&d);
			addEdge(a,b,-d);
		}
		int ok=0;
		for(int i=1; i<=n; i++) {
			if(spfa(i)) {
				ok=1;
				break;
			}
		}
		if(ok)
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}

• Re:关于用spfa，为什么我开的数组大小不同，结果不同 (1612) 16202120 2017-06-12 16:23:57