本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-25 08:33:13

[ABC368E] Train Delay

题目考察：图论建模，思维，双指针。
题目简述：
有 $m$ 辆火车在 $n$ 个城市间穿梭，对于第 $i$ 辆火车，他会在 $s_i$ 时刻从 $a_i$ 城市出发，在 $t_i$ 时刻从到达 $b_i$ 城市。
现在第 $1$ 辆火车推迟了 $ans_1$ 单位时间，问在使得推迟总时间最小的情况下，怎样使原本可以换乘的火车现在还可以换乘（换乘不需要时间）。
数据范围：

• $2\le n,m\le 2\times 10^5$
• $\forall i\in[1,m],1\le a_i,b_i\le n,a_i\ne b_i$
• $\forall i\in[1,m],0\le s_i<t_i\le 10^9$
• $1\le ans_1\le 10^9$

要想直接跑拓扑的话，轻轻松松就卡成 $\Theta(n^2)$ 了，不可行。

那么我们发现瓶颈是在拓展以下式子而变慢的： $$ans_v=max(0,ans_u+t_u-t_v)$$ 但是我们发现，$ans_u+t_u$ 这部分都是一样的，那么我们可以将其记录在 $b_u$ 这个点上，当拓展这个式子时从这个点上取值计算就可以了。

当然，$t_u\le s_v$ 的才有贡献，那么我们复制一份火车时程表，一个按 $s_i$ 排序，一个按 $t_i$ 排序，跑一个类似于双指针的东西就可以了。

时间复杂度为 $\Theta(m\log m)$，瓶颈在排序。

代码