P1613 跑路

题目大意

一张有 $n$ 个顶点，$m$ 条边的单向图。人在图上行走，每一秒可以走 $2^k$（$k$ 是任意自然数）步。请问从 1 走到 $n$ 最少花费时间是多少。

分析

设从 1 走到 $n$ 最少花费方案为 { 1 , a 1 , a 2 , . . . , a p , n } \{1,a_1,a_2,...,a_p,n\} {1,a1​,a2​,...,ap​,n}。其中，$a_i$ 代表的是每次走到的顶点编号。

当 $a_p=i$ 时（需要存在 $w(i,n)$ 满足 $2^j$ 的距离）。方案变为： { 1 , a 1 , a 2 , . . . , a p − 1 , i , n } \{1,a_1,a_2,...,a_{p-1},i,n\} {1,a1​,a2​,...,ap−1​,i,n}。方案的属性：

1. 目的地。子方案的目的地为 $i$。
2. 花费时间。原方案花费的时间 = 子方案花费的时间 + 1。因此，子方案求解的也是最少花费时间。

综上所述，子方案反映的问题是从 1 ~ $i$ 的最少花费时间。满足动态规划性质。不过，由于是在图中，考虑用 floyd、dij、spfa 去实现动态规划。

在这个过程中，我们还需要判断 $(i,n)$ 是否存在一条 $2^j$ 的路径。因此，可以预处理一个 st 数组，其中 st[i][j][k] 代表从顶点 $i$ 到 $j$ 是否存在一条 $2^k$ 的路径。显然，这可由倍增优化实现。