思路解析 问题本质 带修改的单源最短路：边权只会递增（+1），需要在修改后高效地更新最短路。 为什么不能暴力重跑 DIJKSTRA？ * n, m ≤ 10⁵，Dijkstra 一次 O(m log n) ≈ 1.7×10⁶ * q ≤ 2000 次修改，全部重跑：3.4×10⁹，超时 核心技巧：势函数 + DIAL 最短路 关键观察：每次修改只是将若干条边权 +1，旧最短路 d[v] 离新最短路 d'[v] 很近。 定义 δ[v] = d'[v] − d[v]（距离增量），可以证明： > 任意可达节点 v，δ[v] ≤ n − 1 证明：旧最短路径最多 n−1 条边，其中每条边权最多增加 1，所以旧路径的新代价 ≤ d[v] + (n−1)。新最短路 ≤ 旧路径新代价，故 δ[v] ≤ n−1。 利用势函数将边权缩小：定义缩减权 r(u,v)=w′(u,v)+d[u]−d[v]≥0r(u,v) = w'(u,v) + d[u] - d[v] \geq 0r(u,v)=w′(u,v)+d[u]−d[v]≥0 求 δ[v]（从源点出发的缩减权最短路）即可。因为 δ 值有界（≤ n−1），可以用 Dial 算法（桶排序最短路），复杂度 O(n + m) 每次！ 总复杂度 步骤 复杂度 初始 Dijkstra O(m log n) 每次修改后重算 O(n + m) 总计 O(m log n + q·(n + m)) ≈ 4×10⁸ ✓ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 逐行注释代码