AGC072E

帅爆了这个题。

二分答案，初始有 $x$ 的钱，转换为判定性问题。不妨先考虑链的情况，一个结论是，每次将里程换成钱时要么全部换完，要么换到的钱能恰好使用到下一次兑换；否则考虑调整，设两次相邻的兑换分别在 $x,y$，且在 $x$ 处既没有把里程用尽，到 $y$ 时钱也没有用完，则必然可以取一个 $\varepsilon>0$，将 $x$ 处兑换的里程数增加/减小 $\varepsilon$，必有一者更优。

将每个点细拆成到达和离开时刻，则在每个兑换点上，要么其离开时刻里程为 $0$，要么在下一个兑换点的到达时刻钱为 $0$。离开时刻里程为 $0$ 的兑换点称为 A 类特殊点，将到达时刻钱为 $0$ 的点称为 B 类特殊点，则相邻两特殊点间至多隔了一个兑换点，那一个兑换点的情况这仅在两特殊点分别为 A、B 时产生。则令 $f_i,g_i$ 分别为 $i$ 作为 A/B 类特殊点时，离开时最多拥有多少钱/里程；转移考察 $(i,j)$ 为 $\{\tt A,B\}^2$ 的四种情况。

将判定性问题的解法拓展到一般图，显然两交换点间肯定走关于钱的最短路，确定所有兑换点后直接退化到链的情况，故上述所有结论仍然成立！记 $d_{u,v}$ 为 $(u,v)$ 间钱最短路长度，这里给出详细的转移：

使用 Bellman-Ford 模拟上述过程，松弛一个点再转移复杂度为 $\mathcal{O}(n^2)$。由于成环必然不优，故松弛总轮数不超过 $n$ 次，总复杂度为 $\mathcal{O}(n^4\log{V})$。

注意到最终答案下，$f_n$ 的值固定为 $0$，将上述 dp 倒序（并非转置原理，这里不是简单的线性变换），记 $f_u,g_u$ 为 $u$ 作为 A/B 类点，想要到达 $n$ 得最少有的钱/里程，转移即对以上的 dp 解不等式，得：

如此可以去掉二分，直接求解。但复杂度是 $\mathcal{O}(n^4)$ 仍然无法接受。

一个性质是，在旅行过程中，钱 + 里程 $\times F$ 的值不增。走过一段路时该值不变，进行兑换时由于 $R_*<F$ 故该值减少。在上述恰好相反的 dp 过程中，将 $f_u/g_u$ 分别赋权值 $f_u,g_u\times F$，每次取出权值最小的，拿他取松弛其余点，则按照该顺序，一个被取出过的点不会再被其他点松弛（将 $f_u,g_u$ 即 $1\to u$ 的最终状态为 $(f_u,0)$ 和 $(0,g_u)$ 的路径）！这相当于一个 dijkstra 的过程。复杂度降至 $\mathcal{O}(n^3)$。