设 f [ i ] [ j ] [ k ] 为表示从 i 到 j 是否有一条 $2^k$ 长度的路径
那么像 Floyd 一样枚举中转点，起点，终点转移就好了：
if （f [ a ] [ b ] [ k-1 ] && f [ b ] [ c ] [ k-1 ] ） f [ a ] [ c ] [ k ] = 1
设 dis [ i ] [ j ] 表示 i 到 j 的距离，初始如果 i 到 j 有长度为 $2^k$ 的路径 dis [ i ] [ j ] =1
然后跑 Floyd 更新 dis，最后输出 dis [ 1 ] [ n ]
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=65; int n,m; int dis[N][N]; bool f[N][N][N]; inline void pre()//预处理f { for(int i=1;i<N;i++)//枚举长度2^i for(int k=1;k<=n;k++)//枚举中转点 for(int u=1;u<=n;u++)//枚举起点 for(int v=1;v<=n;v++)/*枚举终点*/ if(f[u][k][i-1]&&f[k][v][i-1]) f[u][v][i]=dis[u][v]=1; } int main() { memset(dis,0x3f,sizeof(dis));//初始化 int a,b; n=read(); m=read(); for(int i=1;i<=m;i++) a=read(),b=read(),f[a][b][0]=dis[a][b]=1; pre(); 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][j],dis[i][k]+dis[k][j]);//跑Floyd printf("%d",dis[1][n]); return 0; }
原文：https://www.cnblogs.com/LLTYYC/p/9854542.html