?多組數(shù)據(jù)不清零——見祖宗?

「3.3」蟲洞 Wormholes

問題背景

「一本通3.3 練習2」

題目描述

John 在他的農(nóng)場中閑逛時發(fā)現(xiàn)了許多蟲洞。蟲洞可以看作一條十分奇特的有向邊，并可以使你返回到過去的一個時刻（相對你進入蟲洞之前）。John 的每個農(nóng)場有 M 條小路（無向邊）連接著 N（從 1 到 N 標號）塊地，并有 W 個蟲洞。

現(xiàn)在 John 想借助這些蟲洞來回到過去（在出發(fā)時刻之前回到出發(fā)點），請你告訴他能辦到嗎。 John 將向你提供 F 個農(nóng)場的地圖。沒有小路會耗費你超過 10^4 秒的時間，當然也沒有蟲洞回幫你回到超過 10^4 秒以前。

輸入格式

第一行一個整數(shù)?F，表示農(nóng)場個數(shù)；
對于每個農(nóng)場：
第一行，三個整數(shù)?N,M,W；
接下來?M?行，每行三個數(shù)?S,E,T，表示在標號為?S?的地與標號為?E?的地中間有一條用時?T?秒的小路；
接下來?W?行，每行三個數(shù)?S,E,T，表示在標號為?S?的地與標號為?E?的地中間有一條可以使?John?到達?T?秒前的蟲洞。

輸出格式

輸出共?F?行，如果?John?能在第?i?個農(nóng)場實現(xiàn)他的目標，就在第?i?行輸出?YES，否則輸出?NO。

樣例輸入1

2
3?3?1
1?2?2
1?3?4
2?3?1
3?1?3
3?2?1
1?2?3
2?3?4
3?1?8

樣例輸出1

NO
YES

注釋說明

對于全部數(shù)據(jù)，1≤F≤5， 1≤N≤500， 1≤M≤2500， 1≤W≤200,1≤S,E≤N， ∣T∣≤10^4。

#include<bits/stdc++.h>
using namespace std;
int n,m,dis[100005],a,b,c,huan[100005],w,t;
bool bl[100005];
struct ed {int to,w;
};
vector<ed>e[100005];
void spfa(int s){deque<int>q;memset(dis,0x3f,sizeof(dis));memset(bl,0,sizeof(bl));memset(huan,0,sizeof(huan));q.push_back(s);bl[s]=1;huan[s]++;dis[s]=0;while(!q.empty()) {int k=q.front();q.pop_front();bl[k]=0;int o;for(int i=0; i<e[k].size(); i++){o=e[k][i].to;if(e[k][i].w+dis[k]<dis[o]){dis[o]=e[k][i].w+dis[k];if(bl[o]==0){if(q.empty()||dis[o]<q.front())q.push_front(o);else q.push_back(o);bl[o]=1;huan[o]++;if(huan[o]>n){puts("YES");return;}}}}}puts("NO");
}
int main() {scanf("%d",&t);while(t--) {scanf("%d%d%d",&n,&m,&w);for (int i = 0; i <= 501; i++) e[i].clear();for(int i=1; i<=m; i++) {scanf("%d%d%d",&a,&b,&c);e[a].push_back((ed){b,c});e[b].push_back((ed){a,c});}for(int i=1; i<=w; i++) {scanf("%d%d%d",&a,&b,&c);e[a].push_back((ed){b,-c});}for (int i=1;i<=n;i++)e[0].push_back((ed){i,0});spfa(0);}
}
/*
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8NO
YES
*/