这篇文章上次修改于 464 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 1150 个字，阅读时长 ≈ 3 分钟

P1613 跑路

题目链接

题意

一个有向图，每条边长度均为一千米，每秒可以走 $2^k$ 千米（k为任意自然数）且不能中途停下，也就是要走就走恰好 $2^k$ 千米，问几秒钟能恰好从1到n。

思路

看到 $2^k$，可以往倍增的方向去想，考虑找出所有 $2^k$ 次方长度的路径，并将这个路径的起点和终点连一条边权为1的边，跑最短路即可。找路径时枚举中间点，如果起点到中间点以及中间点到终点均存在长度 $2^{k-1}$ 的路径，那么起点到终点自然存在长度为 $2^k$ 的路径。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<climits>
#ifdef ONLINE_JUDGE
#define debug(x)
#else
#define debug(x) cout<<' '<<#x<<'='<<x<<endl
#endif
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=60,inf=INT_MAX>>1;
int n,m;
int a[N][N];
bool f[N][N][65];
int main()
{
    n=read();
    m=read();
    //初始化以及读入边
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j) a[i][j]=inf;
    for(int i=0;i<m;++i){
        int u=read(),v=read();
        a[u][v]=1;
        //u到v有长度为1的路径
        f[u][v][0]=1;
    }
    //枚举k的大小以及三个点
    //起点、中间点、终点
    //k不用太大64就够了
    for(int k=1;k<64;++k)
        for(int i=1;i<=n;++i)
            for(int o=1;o<=n;++o)
                for(int j=1;j<=n;++j)
                    if(f[i][o][k-1]&&f[o][j][k-1]){
                        //如果两边都存在长度为2^k-1的
                        //路径那么就存在长度为2^k的路径
                        f[i][j][k]=1;
                        a[i][j]=1;
                    }
    //直接跑floyd
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    printf("%d\n",a[1][n]);
    return 0;
}