Luogu P1613 跑路

题目
先倍增预处理怎么那些点对之间可以一次到。
然后拿处理出来的这个东西跑floyd。

#include<bits/stdc++.h>
#define N 53 
using namespace std;
int dis[N][N],a[N][N][N];
int read(){int x;scanf("%d",&x);return x;}
int min(int a,int b){return a<b? a:b;}
int main()
{
    memset(dis,0x3f,sizeof dis);
    int n=read(),m=read(),i,j,k,t,u,v;
    for(i=1;i<=m;++i) u=read(),v=read(),dis[u][v]=1,a[u][v][0]=1;
    for(t=1;t<=32;++t) for(i=1;i<=n;++i) for(k=1;k<=n;++k) for(j=1;j<=n;++j) if(a[i][k][t-1]&&a[k][j][t-1]) a[i][j][t]=dis[i][j]=1;
    for(k=1;k<=n;++k) for(i=1;i<=n;++i) for(j=1;j<=n;++j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    return !printf("%d",dis[1][n]);
}

Luogu P1613 跑路

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/11773913.html