解题思路
倍增$floyd$，首先设$f[i][j][k]$表示$i$这个点到$j$的距离能否为$2^k$，初值是如果x,y之间有边，那么$f[x][y][0]=1$。转移方程就是$f[i][j][t]|=(f[i][k][t-1]\&f[k][j][t-1])$，就是传递闭包。因为跑步机只能到$2^k$，那么就把所有$f[i][j][k]=1$的(i，j)之间连一条距离为1的边，最后跑一个最短路。
#include<iostream> #include<cstdio> #include<cstring>using namespace std; const int MAXN = 55;inline int rd(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return f?x:-x; }int dis[MAXN][MAXN],n,m; bool f[MAXN][MAXN][66];int main(){memset(dis,0x3f,sizeof(dis));n=rd(),m=rd();int x,y;for(int i=1;i<=m;i++){x=rd(),y=rd();f[x][y][0]=1;dis[x][y]=1;if(x==y) {putchar('1');return 0;}}for(int t=1;t<=64;t++)for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(f[i][k][t-1] && f[k][j][t-1]){f[i][j][t]=1;dis[i][j]=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][j],dis[i][k]+dis[k][j]);cout<<dis[1][n];return 0; }