小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 6:006:00 之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑 2^k2
k
千米（kk 是任意自然数）。当然，这个机器是用 longint 存的，所以总跑路长度不能超过 maxlongint 千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点 11，公司为点 nn，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证 11 到 nn 至少有一条路径。
输入格式
第一行两个整数 n,mn,m，表示点的个数和边的个数。
接下来 mm 行每行两个数字 u,vu,v，表示一条 uu 到 vv 的边。
输出格式
一行一个数字，表示到公司的最少秒数。
样例
输入数据 1
4 4
1 1
1 2
2 3
3 4
输出数据 1
1
提示
样例解释
1 \to 1 \to 2 \to 3 \to 41→1→2→3→4，总路径长度为 44 千米，直接使用一次跑路器即可。
数据范围
50%50% 的数据满足最优解路径长度 \leq 1000≤1000；
100%100% 的数据满足 2\leq n \leq 502≤n≤50，m \leq 10 ^ 4m≤10
4
，最优解路径长度 \leq≤ maxlongint。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
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 x*o;
}
const int N=55;
int dis[N][N],f[N][N][N];
int main(){
memset(dis,0x3f,sizeof(dis));//初始化无穷大
int n=read(),m=read();
for(int i=1;i<=m;++i){
int a=read(),b=read();
dis[a][b]=1;f[a][b][0]=1;//初始化
}
for(int p=1;p<=30;++p)
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(f[i][k][p-1]&&f[k][j][p-1]){//同时更新
dis[i][j]=1;
f[i][j][p]=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]=min(dis[i][j],dis[i][k]+dis[k][j]);
printf("%d\n",dis[1][n]);
return 0;
}