前置芝士：最短路、floyd 传递闭包、倍增
思路
看到题目里面的一次能走 \(2^k\) 千米，我们联想到倍增，因为只能用跑路器。
我们枚举 \(k\)，然后做一次传递闭包，\((i,j)\) 走 \(2^k\) 千米是相连的，当且仅当有一个点 \(k\) 是的 \((i,k),(k,j)\) 可以通过走 \(2^{k-1}\) 千米相连。此时，\((i,j)\) 的距离为 \(1\)。
\(n\) 不大，跑 floyd 就好了。
时间复杂度：\(O(wn^3)\)，其中 \(w\) 是 int 位数。
难点/坑点：
- 不要将自己和自己设置为走 \(2^0\) 步相连的，因为自己到自己并没有步数，在跑 floyd 传递闭包时可能会遇到 \(i=k\) 的情况（\(k\) 是第一个枚举的，\(i\) 是第二个），那么就会有 \((i,j)\) 明明是走 \(2^{k-1}\) 步相连的推出 \((i,j)\) 是走 \(2^k\) 步相连。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define int ll
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1);
for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }
const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }
#define maxn 55
int n,m;
vector<int> G[maxn];
bool vis[35][maxn][maxn];
int f[maxn][maxn];
void work() {
mem(f,0x3f);
in2(n,m);
For(i,1,n) f[i][i]=0;
For(i,1,m) {
int u,v;
in2(u,v);
vis[0][u][v]=1;
f[u][v]=min(f[u][v],1ll);
}
For(x,1,32) For(k,1,n) For(i,1,n) For(j,1,n)
if(vis[x-1][i][k]&&vis[x-1][k][j])
vis[x][i][j]=1,f[i][j]=min(f[i][j],1ll);
For(k,1,n) For(i,1,n) For(j,1,n)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
cout<<f[1][n];
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
int _=1;
// int _=read();
For(i,1,_) {
work();
}
return 0;
}