Luogu1613 跑路

一直不会倍增qwq

怒做(chao)一(ti)发(jie)qwq

(f(i,j,k))表示从(i)到(j)的距离是否可以等于(2^k)，等于就连边

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n, m;
int f[55][55][65];
int dis[55][55];
inline int qr(){
	int x=0;
	char ch=getchar();
	for(;!isdigit(ch); ch=getchar());
	for(; isdigit(ch); ch=getchar()) x=(x<<3)+(x<<1)+ch-48;
	return x;
}
int main(){
	n=qr(),m=qr();
	int u, v;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(i!=j)dis[i][j]=0x3f3f3f;
	for(int i=1; i<=m; i++){
		u=qr(), v=qr();
		dis[u][v]=1;
		f[u][v][0]=1;
	}
	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(f[i][t][k-1]&&f[t][j][k-1]){
						f[i][j][k]=1;
						dis[i][j]=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][j], dis[i][k]+dis[k][j]);
	printf("%d", dis[1][n]);
	return 0;
}

然后，我还是不会倍增qwq