洛谷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;
}