今日题目：跑路
题目分析
题目难度：⭐️⭐️⭐️
题目涉及算法：最短路，倍增。
ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力
题解报告：
1.思路
直接最短路还不行，要上一个倍增，直接用s保存是否存在2^k的路径，处理一下一秒能到的俩边，因为数据不大我用的最暴力的Floyd
2.代码
#include<bits/stdc++.h> using namespace std; int dist[100][100],n,m; bool s[100][100][100]; void floyd() { for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } } } } int main() { memset(dist,10,sizeof(dist)); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); dist[x][y]=1; s[x][y][0]=true; } for(int k=1;k<=64;k++) { for(int i=1;i<=n;i++) { for(int t=1;t<=n;t++) { for(int j=1;j<=n;j++) { if(s[i][t][k-1]&&s[t][j][k-1]) { s[i][j][k]=true; dist[i][j]=1; } } } } } floyd(); cout<<dist[1][n]; return 0; }
