Wormholes——SPFA判定マイナスリング

タイトル:
ジョンが農場をぶらぶらしている間に多くの虫の穴を見つけたと説明した.虫の穴は非常に奇妙な縁と見なすことができます過去の時刻(虫の穴に入る前に)に戻ることができます.ジョンの各農場にはN(1...N記号から)ブロックに接続されたM本の小道があり、W個の虫の穴があります.そのうち1<=N<=500、1<=M<=2500、1<=W<=200です.ジョンはこれらの虫の穴を借りて過去に戻りたいと思っています.(出発時刻までに)、できるか教えてください.ジョンはF(1<=F<=5)農場の地図を提供します.小道がないと10000秒を超える時間がかかります.もちろん、虫の穴が10000秒を超える前に戻ってくることもありません.
入力

Line 1:1つの整数Fで、農場の個数を表す.

Line 1 of each farm:3つの整数N,M,W.

Lines 2…M+1 of each farm:3つの数(S,E,T).Sと表記された地とEと表記された地の間にT秒の小道があることを示す.

Lines M+2…M+W+1 of each farm:3つの数(S,E,T).Sと表記された地とEと表記された地の間にJohnをT秒前に到達させることができる虫穴があることを示す.

しゅつりょく

Lines 1...F:ジョンがこの農場で目標を達成できれば「YES」を出力し、そうでなければ「NO」

を出力する
サンプル入力2/2組データ3 3 3 3 1//3点、3本無方向エッジ、1本有向エッジ(負重みエッジ)1 2 2 1 3 4 2 3 1 3 1 3 3 3 3 1 1 2 3 3 3 3 4 1 8出力NO YES
ヒントFor farm 1,FJ cannot travel back in time.For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.
この問題の意味は、無方向図を与え、k本の負のエッジを与え、この図に負のループがあるかどうかを判断することである.
負のループといえばDijは灰色のまま離れているだけで、負のループを持つ図を処理することはサポートされていないので、私たちはドラえもんの最短アルゴリズムからSPFAを取り出し、各点の出隊回数を記録するしかありません.nより大きいと、負のループが必ず存在します.図のように負のループが存在し、このループの総距離は負で、最短のアルゴリズムは最短を求めるために、この輪を歩き続け、ずっと循環します.
コード:

#include
using namespace std;
struct EDGE {
	int next;
	int to;
	int cs;
} e[99999];
int head[99999];
int num=1;
int d[100000];
int q[999999];
int vis[999999];
int mvp[999999];
int f;
int n,m,w;
int s,e1,t;
void add(int x,int y,int cs) {
	e[num].next=head[x];
	e[num].to=y;
	e[num].cs=cs;
	head[x]=num;
	num++;
}//     
int spfa(int st) {//    
	d[st]=0;
	int h=1,en=2;
	q[h]=st;
	vis[st]=1;
	mvp[st]++;//    ++
	while(h<=en) {
		int v=q[h];//      ，       
		vis[v]=0;//    
		for(int i=head[v]; i!=-1; i=e[i].next) {//      
			if(d[e[i].to]>d[v]+e[i].cs) {//  
				d[e[i].to]=d[v]+e[i].cs;
				if(vis[e[i].to]==0) {//      
					q[en]=e[i].to;//   ，    
					en++;//      
					mvp[e[i].to]++;//    +1
					vis[e[i].to]=1;//  
				}
				if(mvp[e[i].to]>n)return 1;//  n return true
			}
		}
		h++;//      
	}
	return 0;//     ，return flase
}
int main() {
	cin>>f;
	for(int i=1; i<=f; i++) {
		memset(head,-1,sizeof(head));
		memset(e,0,sizeof(e));
		memset(mvp,0,sizeof(mvp));
		memset(q,0,sizeof(q));
		memset(vis,0,sizeof(vis));//    ，     
		num=1;
		for(int j=1; j<=99999; j++)d[j]=1e9;//   
		cin>>n>>m>>w;
		for(int j=1; j<=m; j++) {
			cin>>s>>e1>>t;
			add(s,e1,t);
			add(e1,s,t);
		}
		for(int j=1; j<=w; j++) {
			cin>>s>>e1>>t;
			t=t*-1;//            ，       
			add(s,e1,t);
		}
		if(spfa(1)==1)cout<<"YES"<<endl;//spfa        
		else cout<<"NO"<<endl;
	}
	return 0; 
}