首页 > 代码库 > POJ 3259 Wormholes （判负环）
POJ 3259 Wormholes （判负环）
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 46123 | Accepted: 17033 |
Description
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
23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8
Sample Output
NOYES
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.
Source
题目大意：
FJ有n块农场，编号为1到n，这n块农场由m条道路和w个虫洞连接，没条道路是双向的，权值为t1，表示经过每条道路需要花费t1个时间单位，每个虫洞是单向的，权值为t2，经过每个虫洞可以让你回到t2个时间单位之前（说白了就是时光倒流）；现在问你，FJ想从1号农场开始，经过若干农场后，在其出发之前的某一时刻回到1号农场。现在问你能否实现。
分析：
我们把虫洞上的权值看成负的，这样问题就变成了问你这块农场中是否存在负环的问题了。
单纯spfa跑最短路，判一个点入队超过n次，就有负环，较慢。
这里写一种较快的，dfs版的spfa。详见代码。
AC代码：
#include<cstdio>#include<cstring>#include<algorithm>#define R registerusing namespace std;inline int read(){ R int x=0;bool f=1; R char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return f?x:-x;}const int N=1e5+10;int T,n,m1,m2;struct node{ int v,w,next;}e[N<<1];int tot,head[N],dis[N];bool can,flag[N];void add(int x,int y,int z){ e[++tot].v=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;}void spfa(int x){ flag[x]=1; for(int i=head[x];i;i=e[i].next){ int v=e[i].v,w=e[i].w; if(dis[v]>dis[x]+w){ if(flag[v]||can){can=1;break;} dis[v]=dis[x]+w; spfa(v); } } flag[x]=0;}void Cl(){ can=0;tot=0; memset(dis,0,sizeof dis);//注意不是inf memset(head,0,sizeof head); memset(flag,0,sizeof flag);}int main(){ T=read(); while(T--){ Cl(); n=read();m1=read();m2=read(); for(int i=1,x,y,z;i<=m1;i++){ x=read();y=read();z=read(); add(x,y,z); add(y,x,z); } for(int i=1,x,y,z;i<=m2;i++){ x=read();y=read();z=read(); add(x,y,-z); } for(int i=1;i<=n;i++){ spfa(i); if(can) break; } puts(can?"YES":"NO"); } return 0;}
POJ 3259 Wormholes （判负环）