首页 > 代码库 > POJ 3259 Wormholes（SPFA)

POJ 3259 Wormholes（SPFA)

2024-07-17 00:34:05   225人阅读

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.


练习一下SPFA。

题意：N块地，M条路，W个虫洞。判断有没有可以是时间倒流的路径。

SPFA:判断有没有入队次数超过N的点。Bellman_Ford就直接判断了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=3000*2;
int end[maxn],cost[maxn];
int next[maxn],cnt[maxn],head[maxn];
int t,n,m,w,e;
bool flag;
int d[maxn],visit[maxn];
void add(int u,int v,int w)
{
    end[e]=v;
    cost[e]=w;
    next[e]=head[u];
    head[u]=e++;
}
void SPFA()
{
    queue<int>q;
    memset(visit,0,sizeof(visit));
    memset(cnt,0,sizeof(cnt));
    memset(d,INF,sizeof(d));
    visit[1]=1;
    cnt[1]++;
    d[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int uu=q.front();
        q.pop();
        visit[uu]=0;
        for(int i=head[uu];i!=-1;i=next[i])
        {
            int vv=end[i];
            int ww=cost[i];
            if(d[vv]>d[uu]+ww)
            {
                d[vv]=d[uu]+ww;
                if(!visit[vv])
                {
                    visit[vv]=1;
                    q.push(vv);
                    if(++cnt[vv]>=n)
                    {
                        flag=false;
                        return ;
                    }
                }
            }
        }
    }
    return ;
}
int main()
{
   int x,y,z;
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d%d%d",&n,&m,&w);
       e=0;
       memset(head,-1,sizeof(head));
       for(int i=0;i<m;i++)
       {
           scanf("%d%d%d",&x,&y,&z);
           add(x,y,z);
           add(y,x,z);
       }
       for(int i=0;i<w;i++)
       {
           scanf("%d%d%d",&x,&y,&z);
           add(x,y,-z);
       }
       flag=true;
       SPFA();
       if(!flag)   printf("YES\n");
       else   printf("NO\n");
   }
   return 0;
}
Bellman_Ford：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 3000*2
#define INF 0xFFFFFFF

int t , n , m, w;
int dis[MAXN];
struct Edge{
   int x;
   int y;
   int value;
}e[MAXN];

bool judge(){
     for(int i = 0 ; i < m*2+w ; i++){
        if(dis[e[i].y] > dis[e[i].x] + e[i].value)
          return false;
     }
     return true;
}

void Bellman_Ford(){
     dis[1] = 0;
     for(int i = 2 ; i <= n ; i++)
        dis[i] = INF;
     for(int i = 1 ; i <= n ; i++){
        for(int j = 0 ; j < m*2+w; j++){
           if(dis[e[j].y] > dis[e[j].x] + e[j].value)
             dis[e[j].y] = dis[e[j].x] + e[j].value;
        }
     }
     if(judge())
       printf("NO\n");
     else
       printf("YES\n");
}

int main()
{
   int uu,vv,ww,i;
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d%d%d",&n,&m,&w);
       for(i=0;i<m*2;)
       {
           scanf("%d%d%d",&uu,&vv,&ww);
           e[i].x=uu;
           e[i].y=vv;
           e[i++].value=http://www.mamicode.com/ww;>


联系
我们