A22607.跑路

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

输入格式

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

接下来 mm 行每行两个数字 u,vu,v,表示一条 uuvv 的边。

输出格式

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

输入输出样例

  • 输入#1

    4 4
    1 1
    1 2
    2 3
    3 4
    

    输出#1

    1

说明/提示

【样例解释】

112341 \to 1 \to 2 \to 3 \to 4,总路径长度为 44 千米,直接使用一次跑路器即可。

【数据范围】

50%50\% 的数据满足最优解路径长度 1000\leq 1000

100%100\% 的数据满足 2n502\leq n \leq 50m104m \leq 10 ^ 4,最优解路径长度 \leq maxlongint

首页