首页 > 代码库 > poj3259 Wormholes
poj3259 Wormholes
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 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
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.
题意:N块地,M条路,W个虫洞。判断有没有可以是时间倒流的路径。注意把W次输入的w[i]改成-w[i]。
SPFA:判断有没有入队次数超过N的点。
特别提醒:
不要相信给出的数据范围,这是个大坑!!测试数据绝对有超过很多的,我开了20000的数组。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x3f // 一个大数 #define eps 1e-6 using namespace std; #define maxn 20000 //数组开大些! #define Maxn 20000 int n,m,W; int first[maxn]; int next[maxn]; int u[Maxn]; int v[Maxn]; int w[Maxn]; int dis[maxn]; int go[maxn]; int vist[maxn]; int conut[maxn]; int ttt; queue<int> Q; int spfa(int x) { vist[x]=1; memset(dis,INF,sizeof(dis)); dis[x]=0; Q.push(x); conut[x]++; while(!Q.empty()) { int t=Q.front(); Q.pop(); vist[t]=0; conut[t]++; for(int i=first[t];i!=-1;i=next[i]) { if(dis[t]+w[i]<dis[v[i]]) { dis[v[i]]=dis[t]+w[i]; if(!vist[v[i]]) { if(conut[t]>=n) //如果某点入队超过n次,则可判定存在负环。。。。 return 1; Q.push(v[i]); ++conut[v[i]]; } } } } return 0; } int main() { int T; cin>>T; while(T--) { memset(vist,0,sizeof(vist)); memset(conut,0,sizeof(conut)); while(!Q.empty()) Q.pop(); // cout<<"二货@"<<endl; scanf("%d%d%d",&n,&m,&W); for(int i=1;i<=n;i++) first[i]=-1; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u[i],&v[i],&w[i]); u[i+m]=v[i]; v[i+m]=u[i]; w[i+m]=w[i]; } for(int i=m*2+1;i<=2*m+W;i++) { scanf("%d%d%d",&u[i],&v[i],&w[i]); w[i]=-w[i]; } for(int i=1;i<=2*m+W;i++) { next[i]=first[u[i]]; first[u[i]]=i; } int qq=spfa(1); if(qq) puts("YES"); else puts("NO"); } return 0; }