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 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 requiresT 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
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 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.
思路：最短路，相当于有一个图，每个点之间案由路，但有的路是负的，也就是负环，求的是从1到1花费的时间为负，算法的话就只能选择SPFA算法，其他都不能得出答案。详细步骤见代码。
代码：
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15 #define mod 998244353 16 #define eps 1e-6 17 #define ll long long 18 #define INF 0x3f3f3f3f 19 using namespace std; 20 21 //ma用来存放两个点之间的距离 22 int ma[1010][1010]; 23 //dis用来存放到1之间的距离 24 int dis1[1010]; 25 //vis数组标记已经找过的最大起重 26 bool vis[1010]; 27 28 //m表示有m个点 29 bool spfa(int m) 30 { 31 //qu用来存放需要更新的点 32 queue<int> qu; 33 //初始dis为最大数 34 for(int i=1;i<=m;i++) 35 { 36 dis1[i]=INF; 37 } 38 //初始vis为0，表示所有点都未被记录 39 memset(vis,0,sizeof(vis)); 40 //1不需要记录 41 vis[1]=1; 42 //1到1的距离为0 43 dis1[1]=0; 44 //第一个点为1，入队 45 qu.push(1); 46 //当队伍为空时退出 47 while(!qu.empty()) 48 { 49 int k=qu.front(); 50 qu.pop(); 51 //如果第1个点为负，则表示可以回到离开1 之前的时间 52 if(dis1[1]<0) 53 { 54 return true; 55 } 56 //k的记录被推反，重新记录 57 vis[k]=0; 58 //遍历1到m 59 for(int i=1;i<=m;i++) 60 { 61 //如果1到k之间距离加上k到i将距离比1到i点距离小则更新dis1 62 if((dis1[k]+ma[k][i])<dis1[i]) 63 { 64 //更新dis[i] 65 dis1[i]=dis1[k]+ma[k][i]; 66 //如果i点已被标记则不入队 67 if(!vis[i]) 68 { 69 //由于i点距离被更新，因此需要重新遍历与i连接的点，所以将i点入队，且标记i点 70 qu.push(i); 71 vis[i]=1; 72 } 73 } 74 } 75 } 76 return false; 77 } 78 int main() 79 { 80 //t表示样例数 81 int t; 82 scanf("%d",&t); 83 while(t--) 84 { 85 //n表示点的数量，m表示有几条边，w表示有几个虫洞 86 int n,m,w; 87 scanf("%d %d %d",&n,&m,&w); 88 //a,b表示两个点，c表示从a到b需要的时间 89 int a,b,c; 90 memset(ma,INF,sizeof(ma)); 91 for(int i=1;i<=m;i++) 92 { 93 scanf("%d %d %d",&a,&b,&c); 94 //ab之间是双向路，且两点之间不止有一条路 95 ma[a][b]=ma[b][a]=min(ma[a][b],c); 96 } 97 for(int i=1;i<=w;i++) 98 { 99 scanf("%d %d %d",&a,&b,&c); 100 //虫洞的时间是倒退的所以为负 101 ma[a][b]=min(ma[a][b],-c); 102 } 103 if(spfa(n)) 104 { 105 printf("YES "); 106 } 107 else 108 { 109 printf("NO "); 110 } 111 } 112 }