这道题说每一步可以走2k个距离，那么这道题就直接和倍增建立了联系。
由于n的范围很小，我们可以用Floyd处理边的关系，定义vis[i][j][k]表示ij之间是否存在2k的路径，dis[i][j]表示ij之间的最短距离是多少。
我们可以先进行一次Floyd处理vis，枚举ij以及中间点k，若vis[i][k][l-1]==1且vis[k][j][l-1]==1那么有vis[i][j][l]=1且dis[i][j]=1.
我们在进行一次Floyd，维护dis即可，答案就是dis[1][n].
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 int n,m,dis[60][60],vis[60][60][70]; 8 int main() { 9 cin>>n>>m; 10 memset(dis,0x3f,sizeof(dis)); 11 memset(vis,0,sizeof(vis)); 12 // cout<<dis[1][n]; 13 for(int i=1;i<=m;i++) { 14 int x,y; 15 cin>>x>>y; 16 vis[x][y][0]=1; 17 dis[x][y]=1; 18 } 19 for(int l=1;l<=64;l++) 20 for(int i=1;i<=n;i++) 21 for(int j=1;j<=n;j++) 22 for(int k=1;k<=n;k++) 23 if(vis[j][i][l-1]==1&&vis[i][k][l-1]==1) { 24 vis[j][k][l]=1; 25 dis[j][k]=1; 26 } 27 for(int k=1;k<=n;k++) 28 for(int i=1;i<=n;i++) 29 for(int j=1;j<=n;j++) 30 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 31 cout<<dis[1][n]<<endl; 32 return 0; 33 }
原文：https://www.cnblogs.com/shl-blog/p/10805165.html
