洛谷 P1613 跑路

算法标签: DP、图论、倍增

题目

题目背景

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

题目描述

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

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

输入格式

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

输出格式

输出最少搬运量。

输入输出样例

输入 #1

输出 #1

说明/提示

【样例解释】

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

【数据范围】

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

100%的数据满足n<=50，m<=10000，最优解路径长度<=maxlongint。

题解：

从题目入手，当看到题目中“\(2^k\)”的时候就可以想到这到题的一个技巧——倍增。

假设我们有一些点，若其中的两个点之间距离之和可以到达 \(2^n\) ，那么这两个点之间路程的花费就是 \(1\)，所以在整个图中，所有距离为 \(2^n\) 的一对点之间的边的边权为1。那么问题就变成了如何求哪两个点之间的边权为1。

这里我们采用DP的方式来实现倍增，我们用最外层循环k=1->64，表示2的幂，内层循环i=1->n，j=1->n，t=1->n，来更新某个点是否可以通过一条边权为1的边到达，由此实现倍增过程，具体代码如下：

for (int k = 1; k <= 64; k ++ )
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int t = 1; t <= n; t ++ )
                if (f[j][i][k - 1] && f[i][t][k - 1])
                    f[j][t][k] = dis[j][t] = 1;

之后题目中所给数据满足\(n \le 50\) ，所以在最终求解最短路径时候可以使用Floyd，三层循环求解最短路，最终输出从1-n之间的最短路即可。

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 70;
int n, m;
int f[N][N][N], dis[N][N];
int main()
{
    memset(dis, 0x3f, sizeof dis);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        f[x][y][0] = 1;
        dis[x][y] = 1;
    }
    for (int k = 1; k <= 64; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                for (int t = 1; t <= n; t ++ )
                    if (f[j][i][k - 1] && f[i][t][k - 1])
                        f[j][t][k] = dis[j][t] = 1;
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++ )
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
    printf("%d", dis[1][n]);
    return 0;
}

小A