发现和最短路差不多，不过不能朴素的跑最短路。考虑对于每两个相隔 \(2\) 的整数次幂的点建边，在这个新图上跑最短路就是答案。设 \(f_{i,j,k}\) 表示从点 \(i\) 跳 \(2^k\) 步能否到点 \(j\)，转移方程就是一个普通的倍增。如果点 \(i\) 和点 \(j\) 可以一步到达，那么就在新图上建一条长度为 \(1\) 的边。跑 Floyd 最短路即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 105;
int n, m, dis[MAXN][MAXN]; bool f[MAXN][MAXN][MAXN];
signed main(void) {
cin >> n >> m;
memset(dis, 0x3f, sizeof dis);
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
dis[x][y] = f[x][y][0] = 1;
}
for (int k = 1; k < 105; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int l = 1; l <= n; ++l) {
if (f[j][i][k - 1] && f[i][l][k - 1]) {
dis[j][l] = f[j][l][k] = 1;
}
}
}
}
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
cout << dis[1][n] << endl;
return 0;
}