洛谷P1613 跑路 题解

题目链接：P1613 跑路

题意：

cxy 买了一个空间跑路器，每秒钟可以跑 $2^k$ 千米（$k$ 是任意自然数）。

当然，这个机器是用 long long 存的，所以总跑路长度不能超过 $2^{63}-1$ 千米。

cxy 的家到公司的路可以看做一个有向图，cxy 家为点 $1$，公司为点 $n$，每条边长度均为一千米。

cxy 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到学校。

数据保证 $1$ 到 $n$ 至少有一条路径。

输入格式：

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

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

输出格式：

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

数据范围：

$n \le 50,~m \le 10000$，最优解路径长度 $\le 2^{63}-1$。

倍增好题。注意到贪心不一定是最优的，因此考虑dp。

设 $g_{i,j,k}$ 表示 $i,j$ 之间是否存在恰好 $2^k$ 的路径，则

$$g_{i,j,k} = \bigvee_{l=1}^{n} \left(g_{i,l,k-1} \land g_{l,j,k-1}\right)$$

设 $d_{i,j}$ 为 $i,j$ 间的最短路，则 $d_{i,j} = 1$ 的充分条件为「原图存在边 $i \to j$ 或 $g_{i,j,k} = \mathtt{True}$」

注意到 $n$ 很小，所以直接 $\mathtt{Floyd}$ 即可（不会有人到这一步都没发现吧）

时间复杂度 $\mathcal{O}(kn^3)$ ， $k = 63$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,a,b) for(int i=a; i<=b; i++)
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(65))

bitset<N> g[N][N];
int n,m,d[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    memset(d,0x3f,sizeof(d));
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        d[u][v] = 1; g[u][v][0] = 1;
    }
    rep(k,1,63) rep(i,1,n) rep(j,1,n) rep(l,1,n)
        if(g[i][l][k-1] & g[l][j][k-1])
        { g[i][j][k] = 1; d[i][j] = 1; }
    rep(k,1,n) rep(i,1,n) rep(j,1,n)
        down(d[i][j], d[i][k] + d[k][j]);
    cout << d[1][n] << '\n';
    return 0;
}