题意描述

小$A$的工作不仅繁琐,更有苛刻的规定,要求小$A$每天早上在$6:00$之前到达公司,否则这个月工资清零。

可是小$A$偏偏又有赖床的坏毛病。

于是为了保住自己的工资,小$A$买了一个十分牛$B$的空间跑路器,每秒钟可以跑$2^k$千米($k$是任意自然数)。

当然,这个机器是用$long int$存的,所以总跑路长度不能超过$max(long int)$(即$2146483647$)千米。

小$A$的家到公司的路可以看做一个有向图,小$A$家为点$1$,公司为点$n$,每条边长度均为$1000m$。

小$A$想每天能醒地尽量晚,所以让你帮他算算,他最少需要几秒才能到公司。


输入格式

第一行两个整数$n,m$,表示点的个数和边的个数。

接下来$m$行每行两个数字$u,v$,表示一条$u$到$v$的边。


输出格式

一行一个数字,表示到公司的最少秒数。


Input & Output ‘s examples

Input ‘s eg

4 4
1 1
1 2
2 3
3 4

Output ‘s eg

1

数据范围和约定

对于$50\%$的数据,满足最优解路径长度$< 1000$;

对于$100\%$的数据满足$0< n< 50$,$0< m < 10000$,最优解路径长度$< 2147483647$。

保证一定存在一条从$1$到$n$的路径。


分析

一道倍增版子题。

看到题面中$2^k$,我们不难想到需要倍增求解。

题目中告诉我们任何$2^k$的路径都可以使用跑路器一次性走完,则我们设$map[i][j][k]$表示是否存在一条从$i$到$j$长度为$2^k$的路径。

根据倍增的定义,我们可知,若$map[i][mid][k - 1]$与$map[mid][j][k - 1]$均为$true$,则$map[i][j][k]$为$true$。

因此,我们可以直接使用$Floyd$来判断两点直接是否可以使用跑路器到达。

最后再跑一边$Floyd$,更新一下最短路长度即可。

剩下的见代码注释。


Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100

using namespace std;

int n , m;
int u , v;
bool map[N][N][N];

ll dis[N][N];

void add_edge(int u , int v){
map[u][v][0] = true;
dis[u][v] = 1;
}

void Floyd(){
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]);
}
}
}
}

int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++){ //初始化dis数组
for(int j = 1; j <= n; j ++){
dis[i][j] = 0x3f3f3f3f;
}
}
for(int i = 1; i <= m; i ++){
cin >> u >> v;
add_edge(u , v);
}
for(int c = 1; c <= 64; c ++){ //枚举倍增指数
for(int k = 1; k <= n; k ++){ //利用Floyd思想判断两点之间是否可以到达
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
if(map[i][k][c - 1] && map[k][j][c - 1]){
map[i][j][c] = true;
dis[i][j] = 1;
}
}
}
}
}
Floyd(); //最后更新一遍最短路。
cout << dis[1][n] << "\n";

return 0;
}

THE END