【图论杂题】：B.road [Floyed 倍增]

题目：

团队链接：road
原题链接：LUOGU P1613 跑路

题面：

给定$n$个点$m$条边的有向图，单位时间内可经过$2^k$条边($k\in N^{?}$)，求从点$1$到点$n$耗费的最少时间
范围：
$n<=50,m<=10000$,
数据保证最优解路径长度$<=maxlongint$

样例：

输入：

7 8
1 6
5 1
6 4
4 5
5 2
3 7
7 5
2 3

输出：

2

题解：

这一看$n$的范围，就知道，，，Floyed倍增啊，就是个板子题，，，设$f[i][j][k]=1/0$这就表示从i到j长度为2^i的路径是否存在，预处理类似Floyed的距离：$$f[i][j][l]|=f[i][k][l?1]andf[k][j][l?1]$$，不妨设先走 长的路径，再走短的路径，$dis[i][j]$表示走到第j个点，上次跑路的长度至少为2ⁱ，由于两次跑路长度相同必然不优，所以当前长度 要么不走，要么走一次，$dis[1][n]$即为所求的答案。复杂度为$O(30?n^3)$

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
} 
const int sea=55;
int n,m,f[sea][sea][21];
int dis[sea][sea];
int main()
{
    n=read(); m=read();for(int i=1;i<=m;i++){
    int x,y; x=read(); y=read(); f[x][y][0]=1;}for(int l=1;l<=20;l++)//倍增预处理路径for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j][l]|=f[i][k][l-1]&f[k][j][l-1];memset(dis,0x3f,sizeof(dis));//预处理disfor(int k=0;k<=20;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(f[i][j][k]) dis[i][j]=1;for(int k=1;k<=n;k++)//Floyedfor(int i=1;i<=n;i++)for(int j=1;j<=n;j++) if(dis[i][k]&&dis[k][j])dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);printf("%d\n",dis[1][n]);return 0;
} 

Continue……