洛谷 P1613 跑路【最短路+倍增】

原题链接：https://www.luogu.com.cn/problem/P1613

题目描述

小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 6:00?之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑 2^k?千米（k?是任意自然数）。当然，这个机器是用?longint?存的，所以总跑路长度不能超过?maxlongint?千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点?1，公司为点?n，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证?1?到?n?至少有一条路径。

输入格式

第一行两个整数?n,m，表示点的个数和边的个数。

接下来?m?行每行两个数字 u,v，表示一条?u?到?v?的边。

输出格式

一行一个数字，表示到公司的最少秒数。

输入输出样例

输入 #1

4 4
1 1
1 2
2 3
3 4

输出 #1

1

说明/提示

【样例解释】

1→1→2→3→4，总路径长度为?4?千米，直接使用一次跑路器即可。

【数据范围】

50%?的数据满足最优解路径长度≤1000；

100%?的数据满足 2≤n≤50，m≤1e4，最优解路径长度?≤?maxlongint。

解题思路：

首先我们可以观察到只要i,j之间存在2^k千米的路径那么就可以使用跑路器一秒到达，那么看到2^k这个数字，如果熟悉倍增的人，应该就会想到这个题目很有可能会使用到倍增的思想，然后题目需要求的就是1号点到n号点的所需要的最短时间，看到最短时间我们就可以联想到这个题目可能还和最短路有关，要使用最短路的话，关键是还要看能否建出一个图，图的所有边长是一个时间，然后才可以使用到最短路，从前面的分析我们可以知道如果i到j存在长为2^k的路径，那么i到j就可以1秒到达，也就是说我们可以在i->j建一条时间为1s的边，也就是建一条长为1的边，初始输入的边都是长为1的边，也就是时间为1s的边，将初始输入的边建立在图中，边权都为1，然后可以考虑倍增处理一个数组g[i][j][k]表示i->j是否存在长为2^k的边，只要某个g[i][j][k](1<=k<64)为true,那么就可以在i->j建一条长为1的边，倍增处理完之后这个图就建好了，然后在这个图上跑一遍最短路就可以了，由于这个题目n=50,n非常小，所以可以直接使用floyd求最短路，floyd求最短路比较好些，这里就写floyd了。

本题最关键的一步就是使用倍增的思想进行预处理，然后建图，然后求最短路，想到了倍增预处理这一步这个题目基本上就已经顺利解决了。

大致处理过程如下

1.对输入的边建图。

2.倍增预处理之后进一步建图。

3.建图完成之后使用最短路算法(floyd)求一遍最短路即可。

时间复杂度：时间复杂度的瓶颈在于倍增，倍增处理时间为O(k*(n^3)),k=64,n=50,时间大概是8e6,这个时间是肯定可以过的。

空间复杂度：空间复杂度瓶颈在于预处理数组g数组,空间为O((n^2)*64),这个空间是非常小的，空间是肯定足够的。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n, m;
bool g[N][N][65];  //g[i][j][k]表示i到j之间是否存在长度为2^k的路径
int d[N][N];     //d[i][j]表示i到j几秒可以到达
int main()
{
    cin >> n >> m;
    //初始化
    memset(g, false, sizeof g);
    memset(d, 0x3f, sizeof d);
    while (m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v][0] = true;    //输入中表示的是所有长度为1的边
        d[u][v] = 1;
    }

    //倍增法处理i,j之间是否存在2^k的边
    for (int k = 1; k <= 64; k++)
        for (int i = 1; i <= n; i++)
            for (int u = 1; u <= n; u++)
                for (int j = 1; j <= n; j++)
                {
                    if (g[i][u][k - 1] && g[u][j][k - 1])
                    {
                        g[i][j][k] = true;
                        d[i][j] = 1;
                    }
                }

    //floyd求所有i,j之间的最短路，也就是i,j之间最短几秒可以到达
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    
    //输出答案
    cout << d[1][n] << endl;
    return 0;
}