1613

原题链接 题目重点 1.有向图 2.跑的 路径 最少能被分割为几段长度为\(2^k\)，因为每段路长度为\(1km\) 3.有自边 算法设计思考 1.在无背景、k=0的情况下，这题就是一个普通的dp（即floyd） 2.加上了约束条件，当某两个点的距离为\(2^k\)时，可以在1s内到达 3.相当于 ......

小A买了一个空间跑路器，每秒钟可以跑 2^k千米（k 是任意自然数）。 当然，这个机器是用longint 存的，所以总跑路长度不能超过其范围。 小A的家到公司的路可以看做一个有向图，小A 家为点 1，公司为点 n，每条边长度均为一千米。 小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到 ......

发现和最短路差不多，不过不能朴素的跑最短路。考虑对于每两个相隔 $2$ 的整数次幂的点建边，在这个新图上跑最短路就是答案。设 $f_{i,j,k}$ 表示从点 $i$ 跳 $2^k$ 步能否到点 $j$，转移方程就是一个普通的倍增。如果点 $i$ 和点 $j$ 可以一步到达，那么就在新图上建一条长度 ......