目录
显示
题目链接
https://www.luogu.org/problem/P1613
题解
考虑倍增的做法。
假如点 \(i\) 和点 \(j\) 距离为 \(2^{k-1}\),点 \(j\) 和点 \(l\) 距离也为 \(2^{k-1}\),那么显然点 \(i\) 和点 \(l\) 是可以在 \(1\) 秒内抵达的(因为距离为 \(2^k\))
我们可以先倍增预处理出这些互相可达的边,将边权设为 \(1\),并在处理后的图上跑最短路。
因为 \(n \leq 50\),Floyd显然是最优解了。
#include <cstdio> #include <cstring> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; int f[55][55],g[55][55][55]; int main() { int n,m; memset(f,INF,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); f[x][y]=1; g[x][y][0]=1; } for(int k=1;k<=50;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int l=1;l<=n;l++) if(g[i][j][k-1]&&g[j][l][k-1]) f[i][l]=g[i][l][k]=1; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); printf("%d\n",f[1][n]); return 0; }