自动搬运

查看原文

来自洛谷，原作者为

	Perta broken tower

搬运于2025-08-24 22:55:45，当前版本为作者最后更新于2024-03-19 22:00:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在不新建铁路线的图上跑最短路，定义此时 $x,y$ 间的最短路长为 $dis(x,y)$。

特判掉 $dis(S,T)\leq K$ 的情况（所有方案均合法），此时我们要求的就是满足 $dis(S,u)+L+dis(T,v)\leq K$ 的无序二元组 $(u,v)$ 数量。

令 $a_i=dis(T,i)$，将 $a$ 数组从小到大排序。枚举 $u$，则满足条件的 $v$ 数量有 $p$ 个，其中 $p$ 为最大的满足 $dis(S,u)\leq K-L-a_p$ 的数（不存在则为 $0$），直接 $\rm upper\_bound$ 即可。

答案为 $\sum p$，时间复杂度 $O(m\log m+n\log n)$。

Code

关于上述解法你或许会有个小小的疑惑：若一个二元组 $(u,v)$ 同时满足 $dis(S,u)+L+dis(T,v)\leq K$ 和 $dis(S,v)+L+dis(T,u)\leq K$，这样算不会算重吗？

答案是这种情况不存在。证明比较简单，这里不再展开。