1613
|
611 字
|
2 分钟

P1613 跑路 一道小绿题
虽然这只是一道小绿题但是我觉得还是有必要总结一下的因为不错

题目描述

你有辆很 n i u b i 的汽车一秒钟可以跑 2 的任意整次方的距离
给你一个有向图问：从 1 跑到 n 最短时间（边权都是 1）

先给一会思考一下

思路

首先，题目描述就让我们很容易想到倍增这个算法
我们需要把所有的边都存起来
但是一个问题是，在有向图上倍增……会炸……
很容易想到如果我们进行倍增，图并不支持随机访问（不是树）显然要一个一个跳，一定会炸
所以：一个 dp 的思路就出来了（严格意义上的 dp，但不严格意义上我一般不把他算作 dp）
就是floyd
我们考虑倍增的思想：如果我从 p 点走 2^n-1 到另一个点，再从另一个点走 2^n-1 可以走到 q 点，那就说明我们可以 p->q 走 2^n 距离（就是 1 秒）
那么，我们再运用 floyd 的思路，如果 j 到 i，i 到 k 都是 1 秒，那么 j 到 k 就是 1 秒
我们只需要再 floyd 的三重循环外面加一个循环对倍增的那一维进行判断就可以了
floyd 之后：
我们已经求出了那个点到那个点是 1 的距离，但显然我们可能不会起点到终点一定是 1s
所以我们需要跑最短路
在 floyd 求得 dis 数组的基础上，跑一遍最短路，就是最后的最短时间

代码时间

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 70
int n, m;
int dis[maxn][maxn];
int f[maxn][maxn][maxn];
signed main()
{
    memset(dis,0x3f,sizeof(dis));
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        f[a][b][0] = 1;
        dis[a][b] = 1;
    }
    for (int u = 1; u <= 64; u++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= n; k++)
                    if (f[j][i][u - 1] && f[i][k][u - 1])
                        f[j][k][u] = 1,
                        dis[j][k] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
    cout << dis[1][n] << endl;
    return 0;
}

完结撒花
还蛮有意思的一道题……

上一篇
下一篇