P10053 [JOISC 2021 Day2] 逃走経路 题解

· · 题解

题目分析

记 f_{i,j}(x) 表示在时刻 x 从 i 出发去 j 的最早到达时间，g_{i,j}(x) 表示在时刻 x 从 i 出发去 j 最少花费的时间。那么观察结论：

  1. 当 f_{i,j}(x) 与 x 不在同一天时，f_{i,j}(x) 是至多 n 段的分段函数，因为这仅与出发那天能到达的城市集合有关。

  2. 否则，g_{i,j}(x) 是至多 m 段的分段函数，因为其仅与当天能够使用的边集有关。

于是我们只需要对两种情况分别处理：

  1. 首先对每个有序对 (i,j) 预处理出想在一天内从 i 到 j 的最晚出发时间 t_{i,j}，这可以通过建反图跑最短路实现（钦定在一天的末尾到达 j 不影响结果）。

    然后再处理在一天起始时出发的全源最短路。对每个询问把两部分拼起来即可（答案就是 S-T_j+\min\{dis(i,v_j)\mid t_{u_j,i}\ge T_j\}）。

  2. 考虑将每条边 (A_i,B_i) 消失的时间 C_i 作为关键时刻，以每个关键时刻作为出发时间跑出正反图上以 B_i 为起点的最短路，然后拼起来分段取最小值就好。

    感性理解它挺对的，因为 g_{i,j} 的每个端点都代表着一次路径的改变，而路径发生改变当且仅当该路径上的一条边恰好在通过时消失，于是枚举每条“恰好要消失”的边应当具有正确性。

从每个步骤看，时间复杂度大概不超过 O(nm\log m+n^3+qn+m^2\log m+n^2m+q\log m)，应当足够通过本题。

不过我是口胡选手，没有写代码，如果有锅请指出。