本文共 3129 字,大约阅读时间需要 10 分钟。
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 38920 | Accepted: 14307 |
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
Output
Sample Input
23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8
Sample Output
NOYES
Hint
Source
#include#include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f struct Edge{ int f,t,c; }edge[6000]; int dist[505]; int cas,n,m,h,cnt; int bellman() { fill(dist,dist+503+1,inf); dist[1]=0;int j; for(j=1;j<=n;j++) { bool flag=false; for(int i=1;i<=cnt;i++) { int from=edge[i].f,to=edge[i].t,cost=edge[i].c; if(dist[to]>dist[from]+cost) { flag=true; dist[to]=dist[from]+cost; } } if(!flag) break; } if(j==n+1) return 1; else return 0; } int main() { scanf("%d",&cas); while(cas--) { cnt=0; scanf("%d %d %d",&n,&m,&h); int u,v,w; for(int i=1;i<=m;i++) { cnt++; scanf("%d %d %d",&u,&v,&w); edge[cnt].f=u; edge[cnt].t=v; edge[cnt].c=w; cnt++; edge[cnt].f=v; edge[cnt].t=u; edge[cnt].c=w; } for(int i=1;i<=h;i++) { cnt++; scanf("%d %d %d",&u,&v,&w); edge[cnt].f=u; edge[cnt].t=v; edge[cnt].c=-w; } if(bellman()) printf("YES\n"); else printf("NO\n"); } return 0; }
转载地址:http://zvgsi.baihongyu.com/