題干：

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises?N?(1 ≤?N?≤ 500) fields conveniently numbered 1..N,?M?(1 ≤?M?≤ 2500) paths, and?W?(1 ≤?W?≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to?F?(1 ≤?F?≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer,?F.?F?farm descriptions follow.?
Line 1 of each farm: Three space-separated integers respectively:?N,?M, and?W?
Lines 2..?M+1 of each farm: Three space-separated numbers (?S,?E,?T) that describe, respectively: a bidirectional path between?S?and?E?that requires?Tseconds to traverse. Two fields might be connected by more than one path.?
Lines?M+2..?M+?W+1 of each farm: Three space-separated numbers (?S,?E,?T) that describe, respectively: A one way path from?S?to?E?that also moves the traveler back?T?seconds.

Output

Lines 1..?F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

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

Sample Output

NO YES

Hint

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.

題目大意：

有若干個蟲洞，給出了若干普通路徑和其所用時間以及蟲洞的路徑和其倒回的時間，現問你能否回到出發之前的時間，注意普通路徑是雙向的，蟲洞是單向的。

解題報告：

由題目所給信息已經可以構建一張完整的圖了，然后進一步理解題目的意思其實是這張圖是否存在負環，因此使用Bellman_Ford或者spfa即可。

AC代碼：（鄰接表儲存圖）（266ms）

#include<cstdio> #include<algorithm> #include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,cnt; const int MAX = 505; const int INF = 0x3f3f3f3f; int dis[MAX],maze[MAX][MAX],cntt[MAX],head[MAX]; bool vis[MAX]; struct Edge {int to,w,ne;Edge(){}//沒有此構造函數不能寫 node t 這樣Edge(int to,int w,int ne):to(to),w(w),ne(ne){}//可以寫node(pos,cost)這樣} e[200000 + 5];//數組別開小了 void add(int u,int v,int w) {e[cnt].to = v;e[cnt].w = w;e[cnt].ne = head[u];head[u] = cnt++; } bool spfa(int s){dis[s]=0; vis[s]=1; //隊列初始化,s為起點int v;queue<int > q;q.push(s);while (!q.empty()){ //隊列非空v=q.front(); //取隊首元素q.pop();vis[v]=0; //釋放隊首結點，因為這節點可能下次用來松弛其它節點，重新入隊for(int i=head[v]; i!=-1; i=e[i].ne) //對所有頂點{if (dis[e[i].to]>dis[v]+e[i].w) { dis[e[i].to] = dis[v]+e[i].w; //修改最短路if (vis[e[i].to]==0) { //如果擴展結點i不在隊列中，入隊cntt[e[i].to]++;vis[e[i].to]=1;q.push(e[i].to);if(cntt[e[i].to] >=n) return true;}}}}return false; }void init() {cnt = 0;memset(vis,0,sizeof(vis));memset(maze,0,sizeof(maze));memset(e,0,sizeof(e));memset(dis,INF,sizeof(dis));memset(cntt,0,sizeof(cntt));memset(head,-1,sizeof(head)); } int main() {int t;int M,W,u,v,w;cin>>t; while(t--) {init();scanf("%d%d%d",&n,&M,&W);for(int i = 1; i<=M; i++) {scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}for(int i = 1; i<=W; i++) {scanf("%d%d%d",&u,&v,&w);add(u,v,-w);}cntt[1] =1;if(spfa(1)) printf("YES\n");else printf("NO\n");}return 0 ; }

AC代碼2：（鄰接矩陣）（需要判重邊！）（1079ms）

#include<cstdio> #include<algorithm> #include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n; const int MAX = 505; const int INF = 0x3f3f3f3f; int dis[MAX],maze[MAX][MAX],cnt[MAX]; bool vis[MAX]; bool spfa(int s){ // for(int i=0; i<=n; i++) dis[i]=99999999; //初始化每點i到s的距離dis[s]=0; vis[s]=1; //隊列初始化,s為起點int i, v;queue<int > q;q.push(s);while (!q.empty()){ //隊列非空v=q.front(); //取隊首元素q.pop();vis[v]=0; //釋放隊首結點，因為這節點可能下次用來松弛其它節點，重新入隊for(i=1; i<=n; i++) //對所有頂點if (maze[v][i]!=INF && dis[i]>dis[v]+maze[v][i]){ dis[i] = dis[v]+maze[v][i]; //修改最短路if (vis[i]==0){ //如果擴展結點i不在隊列中，入隊cnt[i]++;vis[i]=1;q.push(i);if(cnt[i] >=n) return true;}}}return false; }void init() {memset(vis,0,sizeof(vis));memset(maze,INF,sizeof(maze));memset(dis,INF,sizeof(dis));memset(cnt,0,sizeof(cnt)); } int main() {int t;int M,W,u,v,w;cin>>t; while(t--) {init();scanf("%d%d%d",&n,&M,&W);for(int i = 1; i<=M; i++) {scanf("%d%d%d",&u,&v,&w);if(w<maze[u][v])maze[u][v] = maze[v][u] = w;}for(int i = 1; i<=W; i++) {scanf("%d%d%d",&u,&v,&w);maze[u][v] = -w;}cnt[1] =1;if(spfa(1)) printf("YES\n");else printf("NO\n");}return 0 ; }

?AC代碼3：Bellman_Ford算法（125ms）

//Bellman_Ford算法試試 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define MAXN 3000*2 #define INF 0xFFFFFFFint t , n , m, w; int dis[MAXN]; struct Edge{int x;int y;int value; }e[MAXN];bool judge(){for(int i = 0 ; i < m*2+w ; i++){if(dis[e[i].y] > dis[e[i].x] + e[i].value)return false;}return true; }void Bellman_Ford(){dis[1] = 0;for(int i = 2 ; i <= n ; i++)dis[i] = INF;for(int i = 1 ; i <= n ; i++){for(int j = 0 ; j < m*2+w; j++){if(dis[e[j].y] > dis[e[j].x] + e[j].value)dis[e[j].y] = dis[e[j].x] + e[j].value;}}if(judge())printf("NO\n");elseprintf("YES\n"); }int main() {int uu,vv,ww,i;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&w);for(i=0;i<m*2;){scanf("%d%d%d",&uu,&vv,&ww);e[i].x=uu;e[i].y=vv;e[i++].value=ww;e[i].x=vv;e[i].y=uu;e[i++].value=ww;}for(;i<m*2+w;i++){scanf("%d%d%d",&uu,&vv,&ww);e[i].x=uu;e[i].y=vv;e[i].value=-ww;}Bellman_Ford();}return 0; }

總結：

? ? 1.腦殘了吧調了一下午+一晚上bug嘗試了鄰接矩陣鄰接表，發現是寫了memset(dis,INF,sizeof(INF));這一行樂色？呵呵

? ? 2.如果用鄰接表儲存這題別忘了去重一下不然會wa的，至于為什么權值為負的時候不需要判重，大概是因為這題只要是負的，都不影響結果？因為這題要看的是，是否存在負環啊。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【POJ-3259】 Wormholes（判负环，spfa算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。