| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 28499 | Accepted: 10302 |
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
题意：John的农场里field块地，path条路连接两块地，hole个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。
思路：bellman_ford。由于存在负权边，Dijkstra便不能用了。题目简化下，就是看图中有没有负权环，有的话John可以无限次走这个环，使得时间一定能得到一个负值。所以有的存在负环话就是可以，没有的话就是不可以了。
#include <iostream>
#include <cstdio>using namespace std;#define fMax 505#define eMax 5205#define wMax 99999struct A
{ int sta,end,time;}edge[eMax];int point_num,edge_num,dict[fMax];
bool bellman_ford()
{ for(int i=2;i<=point_num;i++) dict[i]=wMax; for(int i=1;i<=point_num;i++) { bool fals=0; for(int j=1;j<=edge_num;j++) { int v=edge[j].sta; int u=edge[j].end; int w=edge[j].time; if(dict[v]>dict[u]+w) { dict[v]=dict[u]+w; fals=1; } } if(!fals) break; } for(int j=1;j<=edge_num;j++) { int v=edge[j].sta; int u=edge[j].end; int w=edge[j].time; if(dict[v]>dict[u]+w) { dict[v]=dict[u]+w; return 0; } } return 1;}int main()
{ int farm; scanf("%d",&farm); while(farm--) { int field,path,hole; scanf("%d %d %d",&field,&path,&hole); int s,e,t,k=0; for(int i=1;i<=path;i++) { scanf("%d %d %d",&s,&e,&t); edge[++k].sta=s; edge[k].end=e; edge[k++].time=t; edge[k].sta=e; edge[k].end=s; edge[k].time=t; } for(int i=1;i<=hole;i++) { scanf("%d %d %d",&s,&e,&t); edge[++k].sta=s; edge[k].end=e; edge[k].time=-t; } point_num=field; edge_num=k; if(!bellman_ford()) printf("YES\n"); else printf("NO\n");}
return 0;}