首页 > 文章 > [kuangbin带你飞]专题四 最短路练习 F - Wormholes (判断负环)

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

F - Wormholes

题目链接: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算法如下:
//
// 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;
}

 

时间:2019-07-20 01:19:22阅读(28)
联系我们 - 留言反馈
© 2017 版权所有 鲁ICP备17052893号