526互联

P1081 [NOIP2012 提高组] 开车旅行

发布时间 2023-11-30 13:38:52作者: 御坂夏铃

题目有点长，一步一步来。

预处理出每座城市两人分别会选择的下一座城市

用 set 即可实现。

倍增优化 DP

令 \(f_{i,j}\) 表示从城市 \(j\) 出发，行驶 \(2^i\) 天会到达的城市。

令 \(ga_{i,j}\) 表示从城市 \(j\) 出发，行驶 \(2^i\) 天，小 A 行驶的路程。\(gb_{i,j}\) 同理。

答案

枚举每座城市，用倍增加速行驶的过程即可。