题意描述

小$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

Output ‘s eg

数据范围和约定

对于$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;
}