解题思路
倍增$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; }