[洛谷 1613]跑路

题目链接

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;
}