#P1613. 跑路

    ID: 657 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>倍增动态规划dp最短路邻接矩阵

跑路

题目描述

小 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 的边。

输出格式

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

4 4
1 1
1 2
2 3
3 4

1

提示

【样例解释】

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

【数据范围】

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

100%100\% 的数据满足 n50n \leqslant 50m10000m \leqslant 10000,最优解路径长度 \leqslant maxlongint