倍增

可以预处理出来每个点 $i$ 能否跑 $2^p$ 的路程然后到达 $j$ 点

用 $mp_{i,j,p}$ 存出来，最后跑弗洛伊德

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 55
//#define int long long
using namespace std;
int n,m;
bool mp[N][N][70];
int dp[N][N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
signed main(){
	n=reads(),m=reads();
	for(int i=1;i<=m;i++){
		int u,v;
		u=reads(),v=reads();
		mp[u][v][0]=1;
	}
	for(int p=1;p<=65;p++){
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					mp[i][j][p]|=mp[i][k][p-1]&mp[k][j][p-1];
				}
			}
		}
	}
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int p=0;p<=65;p++){
				if(mp[i][j][p]) dp[i][j]=min(dp[i][j],1);
			}
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	printf("%lld\n",dp[1][n]);
	return 0;
}

由每秒钟可以跑2的k次方千米 可以想出倍增思路

定义f[i][j][p]为由i->j的路径是否存在长度为2的p次方千米

由此可以推出dis[i][j] i->j路径的边权

最后用Floyd跑一下最短路就可以了

#include <bits/stdc++.h>
using namespace std;

const int N = 100;

bool f[N][N][N];

long long dis[N][N];

long long n, m;

void read(){
	cin >> n >> m;
	for(long long i = 1;i <= n; i++){
		for(long long j = 1;j <= n; j++){
			dis[i][j] = INT_MAX;
		}
	}
	for(long long i = 1;i <= m; i++){
		long long a, b;
		cin >> a >> b;
		dis[a][b] = 1;
		f[a][b][0] = 1;
	}
	return ;
}

void init(){
	for(long long p = 1;p <= 40; p++){
		for(long long k = 1;k <= n; k++){
			for(long long i = 1;i <= n; i++){
				for(long long j = 1;j <= n; j++){
					if(f[i][k][p-1] && f[k][j][p-1]){
						f[i][j][p] = 1;
						dis[i][j] = 1;
					}
				}
			}
		}
	}
	return ;
}

void compute(){
	init();
	for(long long k = 1;k <= n; k++){
		for(long long i = 1;i <= n; i++){
			for(long long j = 1;j <= n; j++){
				dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	cout << dis[1][n];
	return ;
}

int main(){
	read();
	compute();
	return 0;
}