Wormholes POJ 3259（SPFA判负环）

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

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 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.

题目意思:对于t组输入输出，有N个点，M条双向通路，K个虫洞。虫洞是一个单向的通路。问能否从某一个点出发，通过一些路径和虫洞，返回到出发点，并且时间还要早于出发时间，这样他就能够遇到他自己了。

解题思路：又是John，想都不用想又是USACO的题，美国果然是农业立国啊。在第二组样例中，John沿着1->2->3->1，从第一个点出发回到第一个点，所需时间为-1，这样他就能够遇到自己了。这该怎么思考？遇到虫洞会回到过去，时间回溯。实际上就是要求判断一个带有负权的有向网中是否存在负权值回路，

我们知道可以使用Bellman-Ford可以判断是否存在负环，因为出现了负值回路后会不断的松弛。这里我们用优化后的SPFA来实现。

原理：如果存在负权值回路，那么从源点到某一个点的最短路径可以无限缩短，某些顶点入队列将会超过N次（N为顶点个数）。

ps:代码有给出了另外一种判断是否有负环的方法，时间会更快。从任意一点出发求最短路，必定会求出到其他所有点的最短路，若其中某个点在一个负权回路中，那么它肯定会不断地走这个回路以使到这个点的花费越小越好，这时候该点到出发点的距离就会为负值，所以只需从一个点开始便能找到是否存在负回路，这里我们就只看从源点到源点的dis就可以了。

 #include<cstdio>
 #include<cstring>
 #include<queue>
 #include<algorithm>
 #define INF 0x3f3f3f3f
 #define maxs 10010
 using namespace std;
 struct node
 {
     int to;
     int w;
 } t;
 vector<node>Map[maxs];
 int dis[maxs];
 int vis[maxs];
 int n,m,k;
 void add(int s,int e,int w)
 {
     t.to=e;
     t.w=w;
     Map[s].push_back(t);
 }
 void init()
 {
     int i;
     memset(dis,INF,sizeof(dis));
     memset(vis,,sizeof(vis));
     for(i=; i<=n; i++)
     {
         Map[i].clear();
     }
 }
 int SPFA(int s)
 {
     int cnt[maxs]= {};///记录每个点入队次数
     int i;
     dis[s]=;
     vis[s]=;
     queue<int>q;
     q.push(s);
     cnt[s]++;
     while(!q.empty())
     {
         int u=q.front();
         /*if(cnt[u]>=n)
         {
             return 0;///这里用来判断入队列是否超过N次
         }*/
         q.pop();
         vis[u]=;
         for(i=; i<Map[u].size(); i++)
         {
             int to=Map[u][i].to;
             if(dis[to]>dis[u]+Map[u][i].w)
             {
                 dis[to]=dis[u]+Map[u][i].w;///松弛操作
                 if(dis[]<)///这种判断是否有负环的更快。如果起始点的dis[s]<0说明存在负环
                 {
                     return ;
                 }
                 if(!vis[to])
                 {
                     vis[to]=;
                     q.push(to);
                     cnt[to]++;
                 }
             }
         }
     }
     return ;
 }
 int main()
 {
     int t,i,j,u,v,w;
     scanf("%d",&t);
     for(i=; i<=t; i++)
     {
         scanf("%d%d%d",&n,&m,&k);
         init();
         while(m--)
         {
             scanf("%d%d%d",&u,&v,&w);
             add(u,v,w);
             add(v,u,w);
         }
         while(k--)
         {
             scanf("%d%d%d",&u,&v,&w);
             add(u,v,-w);///虫洞时间取负值
         }
         if(SPFA())
         {
             printf("NO\n");
         }
         else
         {
             printf("YES\n");
         }
     }
     return ;
 }

这里再附上使用邻接矩阵和Bellman-Ford算法的代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
struct Edge
{
    int f;///起点
    int t;///终点
    int c;///距离
} edge[];
int dist[];
int n,m,h,cnt;
int bellman_ford()
{
    memset(dist,inf,sizeof(dist));
    dist[]=;///起点
    int i,j;
    for(j=; j<=n; j++)
    {
        for(i=; i<=cnt; i++)
        {
            if(dist[edge[i].t]>dist[edge[i].f]+edge[i].c)///松弛操作
            {
                dist[edge[i].t]=dist[edge[i].f]+edge[i].c;
            }
        }
    }
    int flag=;
    for(i=; i<=cnt; i++)///遍历所有的边
    {
        if(dist[edge[i].t]>dist[edge[i].f]+edge[i].c)
        {
            flag=;///存在从源点可达的负权回路
            break;
        }
    }
    return flag;
}
int main()
{
    int i,t;
    scanf("%d",&t);
    while(t--)
    {
        cnt=;
        scanf("%d %d %d",&n,&m,&h);
        int u,v,w;
        for(i=; i<=m; i++)
        {
            cnt++;
            scanf("%d %d %d",&u,&v,&w);
            edge[cnt].f=u;
            edge[cnt].t=v;
            edge[cnt].c=w;
            cnt++;
            edge[cnt].f=v;
            edge[cnt].t=u;
            edge[cnt].c=w;
        }
        for(i=; i<=h; i++)
        {
            cnt++;
            scanf("%d %d %d",&u,&v,&w);
            edge[cnt].f=u;
            edge[cnt].t=v;
            edge[cnt].c=-w;
        }
        if(bellman_ford())
            printf("NO\n");
        else
            printf("YES\n");
    }
    return ;
}