题解：P15619 [ICPC 2022 Jakarta R] City Hall

ax_by_c · 2026-03-09 11:50:34 · 题解

不想写代码系列，这场题目有点一言难尽。

跑两遍 dij 求出 f_u,g_u 表示到起点和终点的距离。

特判改了起点及改了终点及不改的情况，这些严格简单于下面部分。

设改的点路径上的前驱后继为 u,v，则代价为 \frac{(H_u-H_v)^2}{4}+f_u+f_v。

枚举改的点及其邻居，将上面的式子拆成一次函数，斜率优化即可。

时间复杂度 O(m\log m)。