传送门
题目理解与强调
给定一个有向图，共有 $n$ 个点和 $m$ 条边，存在自环的情况，每条边的长度都为 $1$ 。与一般题目不同的是，每走一步会走过 $2^k$ 个单位长度（ $k$ 为任意自然数），我们要找的是从点 $1$ 到点 $n$ 中所有路径中需要步数最少的一条。
题解
排除错误算法
第一个想到的方法一定是找到从 $1$ 到 $n$ 的最短路，将最短路的长度转化为二进制，计算其中 $1$ 的个数。
但是很明显，这个算法是错误的，样例都过不了，但是我还是尝试了一下，拿到了 $30\text{pts}$ 。
为什么？因为最短路不一定是二进制数字中 $1$ 的个数最少的方案，例如：我可以通过多次走自环的方式，将步数归为 $1$ ，我也可以走一个较长的路径，但是这一种方案所需要的距离最少。故：最短距离 $\neq$ 最小步数 。
正确方法探讨
本题重点在于善用倍增算法，他的计步方式很特殊，每一步可以跑 $2^k$ 的距离，那么判断一个点 $x$ 到一个点 $y$ 能否只需要走一步就完成，只需要找到一个点 $v$ ，判断是否存在 $d_{x,v}$ （ $d_{i,j}$ 表示由 $i$ 到 $j$ 的一条路径实际长度）是否等于 $d_{v,y}$ 等于 $2^{k-1}$
这样，从 $x$ 点到 $y$ 点的实际距离就可以为 $2^k$ ，只需要一步就可以到。
那么我们规定一个动态规划数组 $dp_{i,j,k}$ ，表示从点 $i$ 到点 $j$ 中是否存在一条实际距离为 $2^k$ 的一条路径。根据上述原理很容易地，我们得到如下代码：
if(dp[i][j][k-1]&dp[j][c][k-1]==1)
{
dp[i][c][k]=1;
dis[i][c]=1;
}
其中的 $dis$ 数组是用来求最短路用的， $dis_{i,j}$ 表示点 $i$ 到点 $j$ 的最少步数。我们将枚举所有起始点、中间点和终点，将所有距离更新即可，当然，第 $dis$ 的三维数组需要从小到大枚举。
由于数据范围很小，又因为我们使用了邻接矩阵存图，所以直接使用 Floyd 算法求 $dis$ 最短路（最小步数）。
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define int128 __int128
#define uint128 unsigned __int128
#define Ld long double
#define reg register
#define space putchar(' ')
#define enter putchar('\n')
#define PI 3.14159265358979323846
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define INF 1000000000000000000
#define N 1010
#define M 1000010
namespace Fast{
template<typename T>inline void read(T &x){
x=0;bool f=false;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=~x+1;
}
template<typename T>inline void print(T x){
int s[65],top=0;
if(x<0)putchar('-'),x=~x+1;
while(x)s[++top]=x%10,x/=10;
if(!top)s[++top]=0;
while(top)putchar(s[top--]+'0');
}
template<typename T,typename...Args>inline void read(T &x,Args&...others){
read(x),read(others...);
}
template<typename T,typename...Args>inline void print(T x,Args...others){
print(x),space,print(others...);
}
const double eps=1e-7;
template<typename T>inline T Abs(T x){return x>0?x:-x;}
template<typename T>inline T Max(T x,T y){return x>y?x:y;}
template<typename T>inline T Min(T x,T y){return x<y?x:y;}
template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
template<typename T>inline void addmod(T &x,T p){if(x>=p)x-=p;}
template<typename T>inline void submod(T &x,T p){if(x<0)x+=p;}
}
using namespace Fast;
int n,m,dis[101][101];
bool dp[101][101][101];
int main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
read(n,m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=inf;
}
}
for(int i=1;i<=m;i++){
int u,v;
read(u,v);
dis[u][v]=1;
dp[u][v][0]=1;
}
for(int k=1;k<=64;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int c=1;c<=n;c++){
if(dp[i][j][k-1]&dp[j][c][k-1]==1)
{
dp[i][c][k]=1;
dis[i][c]=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][k]+dis[k][j],dis[i][j]);
}
}
}
print(dis[1][n]);
return 0;
}
