P1613 跑路
倍增
我们考虑floyd
对于i,j如果有一个中介k使得i->k只用2^p以及k->j只用2^p,那么i->j可以一步到达
最后跑一遍floyd即可
记得是有向图!
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=55; struct node{ int from,to; }; int n,m; int g[N][N][N*2]={0}; ll dis[N][N]; inline ll llmin(ll x,ll y){ return x<y?x:y; } int main(){ memset(dis,33,sizeof(dis)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int from,to; scanf("%d%d",&from,&to); g[from][to][0]=1; dis[from][to]=1; } for(int l=1;l<=64;l++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ if(g[i][j][l-1]&&g[j][k][l-1]) g[i][k][l]=1,dis[i][k]=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]=llmin(dis[i][j],dis[i][k]+dis[k][j]); } } } cout<<dis[1][n]<<endl; return 0; }