P9331 [JOISC 2023 Day1] Passport

Zpair · 2024-04-07 15:41:27 · 题解

注意到可达的点一定构成一段区间，所以问题等价于同时走到 1,n 的最小花费。

先建反图预处理出 1 和 n 到每个点的距离，记为 dis1 和 dis2，这个线段树优化建图然后bfs一遍就行。

考虑钦定最后答案的护照获得顺序，对于当前的可达区间 [l,r]，我们要求在取 [l,r] 之外的点后再也不能取 [l,r] 中的点，容易发现这并不影响答案。

对于当前的 [l,r]，我们最多会在其中取两个点，否则一定会有点的区间被完全包含。

当取两个点 x,y 时，不妨令 L_x \le l,R_y \ge r。则一定存在一组最优解满足 x 走到 1，y 走到 n。因为如果是从 x 走到 n，则当前的 y 可以放在以后选取，这样一定不劣，于是此时答案为 \min(dis1_x+dis2_y+2)。

进一步的，我们不需要枚举选取的两个点 x,y，上面的式子等价于当前区间到 1,n 的距离和。

当取一个点 x 时，不妨令：L_x \le l，另一边的情况类似。

我们断定，将当前可达区间改为 [L_x,R_x] 不影响答案。

当 R_x \ge r 时显然成立。

当 R_x < r 时，被错误标记为不可达的区间为 [R_x+1,r]，根据我们的钦定顺序，这段区间不会影响后面的选取。

当 r=n 时，当前区间的答案可以被取两个点统计到，否则后续的选取一定会有一段覆盖到 n 的区间，则 [R_x+1,r] 的区间被标记为不可达也不会影响答案。

于是可以发现上面的可达区间只有每个点的对应区间，设：f_p 表示从 [L_p,R_p] 开始同时到 1,n 的最小花费，则有：f_p=\min(dis1_p+dis2_p,\min_{p \rightarrow t}(f_t+1))。

按照最短路的更新方式 bfs 一遍即可。

双倍经验：[USACO21DEC] Tickets P。