POJ 3259 Wormholes 图论 贝尔曼-福特算法(Bellman-Ford)

发布时间:2016-12-7 3:50:49 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 3259 Wormholes 图论 贝尔曼-福特算法(Bellman-Ford)",主要涉及到POJ 3259 Wormholes 图论 贝尔曼-福特算法(Bellman-Ford)方面的内容,对于POJ 3259 Wormholes 图论 贝尔曼-福特算法(Bellman-Ford)感兴趣的同学可以参考一下。

Wormholes Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 25757   Accepted: 9254 Description 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 T seconds 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. 这道题是穿越题,穿越。。。题目意思是有个闲的无聊的农夫John(从题目中看农夫不是一般的闲),在自己农场里建了一个图,并且搞了一些正常的路和一些虫洞(就是科幻电影里面经常时光倒流什么什么的路径),并且正常的路是双向路,虫洞是单向的,问农夫从任意一个顶点出发,是否可以当回到此顶点的时候发生时光倒流,即时间小于出发的时间,此题看来还是运用Bellman-Ford算法中负权环的定义,如果图中出现一条负权环的话,则可以说明存在时光倒流的可能,输出YES,不存在负权环的时候,输出NO,这样题目就被愉快的AC了。。。 下面是AC代码: #include<cstdio> #include<iostream> #include<cstring> using namespace std; struct Edge{ int u, v; int time; int flag; }edge[5500]; int dist[600],n,m,w; void relax(int u, int v, int time) { if(dist[v] > dist[u] + time) dist[v] = dist[u] + time; } bool Bellman_Ford() { int i; for(i=1;i<=n;i++) dist[i]=100000; for(i=1; i<=n-1; ++i) for(int j=1; j<=2*m+w; ++j) relax(edge[j].u, edge[j].v, edge[j].time); bool flag = 1; for(i=1; i<=2*m+w; ++i) if(dist[edge[i].v] > dist[edge[i].u] + edge[i].time ) { flag = 0; break; } return flag; } int main() { int i,t; scanf("%d",&t); while(t--) { memset(edge,0,sizeof(edge)); scanf("%d%d%d",&n,&m,&w); for(i=1;i<=2*m;i+=2) { scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].time); edge[i+1].u=edge[i].v; edge[i+1].v=edge[i].u; edge[i+1].time=edge[i].time; } for(i;i<=2*m+w;i++) { scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].time); edge[i].time=-edge[i].time; } if(Bellman_Ford()==0) printf("YES\n"); else printf("NO\n"); } return 0; }