自动搬运

查看原文

来自洛谷，原作者为

	Zpair 诈骗矮人

搬运于2025-08-24 22:47:24，当前版本为作者最后更新于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。