# 跑路
## 题目描述
小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 $6:00$ 之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑 $2^k$ 千米（$k$ 是任意自然数）。当然，这个机器是用 `longint` 存的，所以总跑路长度不能超过 `maxlongint` 千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点 $1$，公司为点 $n$，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证 $1$ 到 $n$ 至少有一条路径。
## 输入格式
第一行两个整数 $n,m$，表示点的个数和边的个数。
接下来 $m$ 行每行两个数字 $u,v$，表示一条 $u$ 到 $v$ 的边。
## 输出格式
一行一个数字，表示到公司的最少秒数。
## 样例 #1
### 样例输入 #1
```
4 4
1 1
1 2
2 3
3 4
```
### 样例输出 #1
```
1
```
## 提示
**【样例解释】**
$1 \to 1 \to 2 \to 3 \to 4$，总路径长度为 $4$ 千米，直接使用一次跑路器即可。
**【数据范围】**
$50\%$ 的数据满足最优解路径长度 $\leq 1000$；
$100\%$ 的数据满足 $2\leq n \leq 50$，$m \leq 10 ^ 4$，最优解路径长度 $\leq$ `maxlongint`。
//将所有的点进行倍增判断,点数不多,以2的64次方为上限,可以这样考虑 //三重循环类似于floyd,然后设置一个中间点 e,如果i能到e,j也能到e,那么i到j就是2的1次方,此时就可以判断为1秒 //然后连图跑最短路即可 #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e4+10,MAXN=100,MAXM=105; int edge[MAXN][MAXN][MAXM]; int e[N],ne[N],h[N],idx; int n,m,res,dist[MAXN]; bool vis[MAXN]; typedef pair<int,int>pii; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dijkstra() { dist[1]=0; priority_queue<pii,vector<pii>,greater<pii>>que; que.push({0,1}); while(!que.empty()){ auto now=que.top(); que.pop(); int dis=now.first,pos=now.second; if(vis[pos]) continue; vis[pos]=true; for(int i=h[pos];~i;i=ne[i]){ int j=e[i]; if(dist[j]>dist[pos]+1){ dist[j]=dist[pos]+1; que.push({dist[j],j}); } } } } signed main() { memset(h,-1,sizeof h); memset(dist,0x3f,sizeof dist); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; scanf("%lld%lld",&u,&v); edge[u][v][0]=1; } for(int k=1;k<=64;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int e=1;e<=n;e++) if(edge[i][e][k-1]==1&&edge[e][j][k-1]==1) edge[i][j][k]=1; for(int k=0;k<=64;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(edge[i][j][k]) add(i,j); dijkstra(); cout<<dist[n]; return 0; }