$$\color{Purple}{kuangbin题解目录}$$

描述

农夫约翰在巡视他的众多农场时，发现了很多令人惊叹的虫洞。

虫洞非常奇特，它可以看作是一条 单向 路径，通过它可以使你回到过去的某个时刻（相对于你进入虫洞之前）。

农夫约翰的每个农场中包含 $N$ 片田地，$M$ 条路径（双向）以及 $W$ 个虫洞。

现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。

他希望能够看到出发之前的自己。

请你判断一下约翰能否做到这一点。

下面我们将给你提供约翰拥有的农场数量 $F$，以及每个农场的完整信息。

已知走过任何一条路径所花费的时间都不超过 $10000$ 秒，任何虫洞将他带回的时间都不会超过 $10000$ 秒。

输入格式

第一行包含整数 $F$，表示约翰共有 $F$ 个农场。

对于每个农场，第一行包含三个整数 $N,M,W$。

接下来 $M$ 行，每行包含三个整数 $S,E,T$，表示田地 $S$ 和 $E$ 之间存在一条路径，经过这条路径所花的时间为 $T$。

再接下来 $W$ 行，每行包含三个整数 $S,E,T$，表示存在一条从田地 $S$ 走到田地 $E$ 的虫洞，走过这条虫洞，可以回到 $T$ 秒之前。

输出格式

输出共 $F$ 行，每行输出一个结果。

如果约翰能够在出发时刻之前回到出发地，则输出 YES，否则输出 NO。

数据范围

$1 \\le F \\le 5$
$1 \\le N \\le 500$,
$1 \\le M \\le 2500$,
$1 \\le W \\le 200$,
$1 \\le T \\le 10000$,
$1 \\le S,E \\le N$

输入样例：

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

输出样例：

NO
YES

思路

• 普通路径是双向的,走双向路需要花费一定时间,虫洞是单向的,走单向路会让时间倒流一定时间,故边最多是$2500\times 2 +20$(空间可适当开大点);
• 求是否可以从起点出发再回到起点,在出发时刻前又回到起点,故转化成求是否有负环,通常用spfa算法解决.
• 另附上floyd算法暴力做法(此题需开$O_2$能过)

代码

• spfa算法

// Problem: 虫洞
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/906/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-26 13:52:48
// 
// Powered by CP Editor (https://cpeditor.org)

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define MAXN 510
#define MAXM 5210

using namespace std;

typedef long long ll;

int t;
int n,m,k;

int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;

int vis[MAXN],cnt[MAXN];
int dist[MAXN];

void add(int a,int b,int c)
{
    ed[idx]=b;
    val[idx]=c;
    nex[idx]=head[a];
    head[a]=idx++;
}

int spfa()
{
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    memset(dist,0,sizeof(dist));

    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        vis[i]=1;
    }

    while(q.size()>0)
    {
        int temp=q.front();
        q.pop();
        vis[temp]=0;

        for(int i=head[temp];i!=-1;i=nex[i])
        {
            int j=ed[i];
            if(dist[j]>dist[temp]+val[i])
            {
                dist[j]=dist[temp]+val[i];
                cnt[j]=cnt[temp]+1;
                if(cnt[j]>=n)
                    return 1;
                if(vis[j]==0)
                {
                    q.push(j);
                    vis[j]=1;
                }
            }
        }
    }
    return 0;
}



int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);

    cin >> t;
    while(t--)
    {
        memset(head,-1,sizeof(head));
        idx=0;
        cin >> n >> m >> k;
        for(int i=1;i<=m;i++)//双向路径
        {
            int a,b,c;
            cin >> a >> b >> c;
            add(a,b,c),add(b,a,c);
        }

        for(int i=1;i<=k;i++)//单向虫洞
        {
            int a,b,c;
            cin >> a >> b >> c;
            add(a,b,-c);
        }

        if(spfa()==1)
            cout << "YES" << endl;
        else cout << "NO" << endl;


    }
    return 0;
}

• floyd算法

// Problem: 虫洞
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/906/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-26 13:52:48
// 
// Powered by CP Editor (https://cpeditor.org)

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#pragma GCC optimize(2)
//注意此处开了O2
#include<iostream>
#include<cstring>
#include<algorithm>

#define MAXN 510

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

int t;
int n,m,k;

int map[MAXN][MAXN];

int floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                if(map[i][j]>map[i][k]+map[k][j])
                    map[i][j]=map[i][k]+map[k][j];
            if(map[i][i]<0)
                return 1;
        }
    return 0;
}




int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);

    cin >> t;
    while(t--)
    {

        cin >> n >> m >> k;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i==j)
                    map[i][i]=0;
                else map[i][j]=inf;
        for(int i=1;i<=m;i++)//双向路径
        {
            int a,b,c;
            cin >> a >> b >> c;
            if(map[a][b]>c)
                map[a][b]=map[b][a]=c;
        }

        for(int i=1;i<=k;i++)//单向虫洞
        {
            int a,b,c;
            cin >> a >> b >> c;
            map[a][b]=-c;
        }

        if(floyd()==1)
            cout << "YES" << endl;
        else cout << "NO" << endl;


    }
    return 0;
}