题意：

小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

题解：

倍增+最短路。

小A的每次移动都可以看做是用一次加速器，那么我们求出哪些点能通过加速器直接连通。

设bool数组f[i][j][k]表示从i到j是否有一条\(2^k\)的路径，若为true，则dis[i][j]=1，倍增这个数组后，跑一遍最短路即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define N 55using namespace std;int dis[N][N];bool f[N][N][40];int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}int main() { memset(dis,63,sizeof(dis)); int n=gi(),m=gi(); for(int i=1; i<=m; i++) { int x=gi(),y=gi(); f[x][y][0]=1; dis[x][y]=1; } for(int k=1; k<=35; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int l=1; l<=n; l++) { f[i][j][k]=(f[i][l][k-1] && f[l][j][k-1]); if(f[i][j][k]) {dis[i][j]=1;break;} } for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); cout<
          
           <