一开始就想着整个过程，觉得逃跑的那个人的路线要考虑好多，包括路径长度，是否脱离追击者的范围要受到额外伤害等等。比较复杂没想明白。
后来发现，可以划分成两个阶段，即追击者传送前后。传送后逃跑者肯定走最短路线最优，因为和追击者的距离变化已经完全固定了，并且传送后的代价可以通过dijk预处理实现 O（1）计算(预处理 n，k 点的单源最短路)
对于传送之前，可以
[EC Final 2022] Chase Game
发布时间 2023-11-11 00:26:36作者: conprour
一开始就想着整个过程，觉得逃跑的那个人的路线要考虑好多，包括路径长度，是否脱离追击者的范围要受到额外伤害等等。比较复杂没想明白。
后来发现，可以划分成两个阶段，即追击者传送前后。传送后逃跑者肯定走最短路线最优，因为和追击者的距离变化已经完全固定了，并且传送后的代价可以通过dijk预处理实现 O（1）计算(预处理 n，k 点的单源最短路)
对于传送之前，可以