[kuangbin带你飞]专题四最短路练习 F - Wormholes （判断负环）

╰半橙微兮° 2023-08-17 15:40 55阅读 0赞

# F - Wormholes #

题目链接：[https://vjudge.net/contest/66569\#problem/F][https_vjudge.net_contest_66569_problem_F]

题目：

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.

**题意：**

农夫约翰在探索他的许多农场，发现了一些惊人的虫洞。虫洞是很奇特的，因为它是一个单向通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。为了帮助FJ找出这是否是可以或不可以，他会为你提供F个农场的完整的映射到（1≤F≤5）。所有的路径所花时间都不大于10000秒，所有的虫洞都不大于万秒的时间回溯。  
  
**Input**  
  
第1行：一个整数F表示接下来会有F个农场说明。 每个农场第一行：分别是三个空格隔开的整数：N，M和W 第2行到M+1行：三个空格分开的数字（S，E，T）描述，分别为：需要T秒走过S和E之间的双向路径。两个区域可能由一个以上的路径来连接。 第M +2到M+ W+1行：三个空格分开的数字（S，E，T）描述虫洞，描述单向路径，S到E且回溯T秒。  
  
**Output**  
  
F行，每行代表一个农场 每个农场单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求。

**思路：**

**套判断负环的模板即可**

**先给出我一开始用的spfa算法如下，用时235s：**

//
    // Created by hanyu on 2019/7/19.
    //
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int maxn=2e5+7;
    #define MAX 0x3f3f3f3f
    int book[maxn],cnt[maxn],d[maxn],head[maxn];
    int n,m,w;
    int pos;
    struct Node{
        int s;
        int e;
        int t;
    }node[maxn];
    void add(int s,int e,int t)
    {
        node[pos].s=e;
        node[pos].e=t;
        node[pos].t=head[s];
        head[s]=pos++;
    }
    bool spfa(int start)
    {
    
        queue<int>qu;
        qu.push(start);
        book[start]=1;
        d[start]=0;
        while(!qu.empty())
        {
            int now=qu.front();
            qu.pop();
            book[now]=0;
            for(int i=head[now];i!=-1;i=node[i].t)
            {
                int ss=node[i].s;
                int ee=node[i].e;
                if(d[ss]>d[now]+ee)
                {
                    d[ss]=d[now]+ee;
                    if(!book[ss])
                    {
                        qu.push(ss);
                        book[ss]=1;
                        cnt[ss]++;
                        if(cnt[ss]>=n)
                        return true;//判断负环
                    }
                }
            }
        }
        return false;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            memset(book,0,sizeof(book));
            memset(cnt,0,sizeof(cnt));
            memset(d,MAX,sizeof(d));
            memset(head,-1,sizeof(head));
            memset(node,0,sizeof(node));
            scanf("%d%d%d",&n,&m,&w);
            int s,e,t;
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d%d",&s,&e,&t);
                add(s,e,t);
                add(e,s,t);
            }
            for(int i=1;i<=w;i++)
            {
                scanf("%d%d%d",&s,&e,&t);
                add(s,e,-t);
            }
            cnt[1]=1;
            pos=0;
            if(spfa(1))
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

**然后学习了优化版的Bellmanford算法，发现速度更快，用时79s**

//
    // Created by hanyu on 2019/7/20.
    //
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int maxn=6005;
    #define MAX 0x3f3f3f3f
    int n,m,w;
    
    int pos;
    int d[maxn];
    
    struct Node{
        int u,v,w;
    }node[maxn];
    void add(int u,int v,int w)
    {
        node[++pos].u=u;
        node[pos].v=v;
        node[pos].w=w;
    }
    bool bell(){
    
        memset(d,MAX,sizeof(d));
        d[1]=0;
        int flag=0;
        for(int i=1;i<=n;i++)
        {
           flag=0;
           for(int j=1;j<=pos;j++)
           {
               if(d[ node[j].v]>d[node[j].u]+node[j].w)
               {
                   d[ node[j].v]=d[node[j].u]+node[j].w;
                   flag=1;
               }
           }
           if(flag==0)
               return false;
        }
        flag=0;
        for(int i=1;i<=pos;i++)
        {
            if(d[node[i].v]>d[node[i].u]+node[i].w)
                return 1;
        }
        return 0;
    }
    int main()
    {
        int T;
        int a,b,c;
        scanf("%d",&T);
        while(T--)
        {
            pos=0;
            scanf("%d%d%d\n",&n,&m,&w);
            for(int i=1;i<=m;i++)
            {
                scanf("%d%d%d",&a,&b,&c);
                add(a,b,c);
                add(b,a,c);
            }
            for(int i=1;i<=w;i++)
            {
                scanf("%d%d%d",&a,&b,&c);
                add(a,b,-c);
            }
            if(bell())
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11216351.html

[https_vjudge.net_contest_66569_problem_F]: https://vjudge.net/contest/66569#problem/F