POJ 3259 Wormholes （判负环）

Wormholes

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 46123		Accepted: 17033

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: A single integer, F. F farm descriptions follow.
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

Lines 1..F: For each farm, output "YES" if FJ can achieve his goal,
otherwise output "NO" (do not include the quotes).

Sample Input

Sample Output

NO

YES

Hint

For farm 1, FJ cannot travel back in time.
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

USACO 2006 December Gold

题目大意：
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 register

using namespace std;

inline int read(){

    R int x=;bool f=;

    R char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return f?x:-x;

}

const int N=1e5+;

int T,n,m1,m2;

struct node{

    int v,w,next;

}e[N<<];

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]=;

    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=;break;}

            dis[v]=dis[x]+w;

            spfa(v);

        }

    }

    flag[x]=;

}

void Cl(){

    can=;tot=;

    memset(dis,,sizeof dis);//注意不是inf

    memset(head,,sizeof head);

    memset(flag,,sizeof flag);

}

int main(){

    T=read();

    while(T--){

        Cl();

        n=read();m1=read();m2=read();

        for(int i=,x,y,z;i<=m1;i++){

            x=read();y=read();z=read();

            add(x,y,z);

            add(y,x,z);

        }

        for(int i=,x,y,z;i<=m2;i++){

            x=read();y=read();z=read();

            add(x,y,-z);

        }

        for(int i=;i<=n;i++){

            spfa(i);

            if(can) break;

        }

        puts(can?"YES":"NO");

    }

    return ;

}

秒客网

POJ 3259 Wormholes （判负环）

相关文章