「CF1253F」Cheap Robot

发表于 更新于 分类于 本文字数： 491 阅读时长 ≈ 2 分钟

Description

Link：CF1253F

给出一个包含 nn 个点 mm 条边的简单无向连通带权图。节点编号为 1∼n1 \sim n，其中恰好有 kk 个充电中心，编号为 1∼k1 \sim k。

有一个电池容量为 cc 的机器人在图中移动，任意时刻电量 xx 必须为区间 [0,c][0, c] 中的整数。经过一条长度为 ww 的边需要消耗 ww 的电量，每当到达一个充电中心时，其电池将会充满。

有 QQ 次询问，每次询问给出 a,ba, b，你需要求出机器人从 aa 到 bb 至少需要的电池容量 cc 是多少。

数据范围：2≤k≤n≤1052 \leq k \leq n \leq 10^5，1≤m,Q≤3×1051 \leq m, Q \leq 3 \times 10^5，1≤w≤1091 \leq w \leq 10^9，1≤a,b≤k1 \leq a, b \leq k，a≠ba \neq b。

时空限制：33s / 512512MiB。

Solution

若所有节点均为充电桩，则从 aa 走到 bb 的答案，即为 a,ba, b 之间所有简单路径上最大边权的最小值。此时只需求出最小生成树，使用树上倍增求出 a,ba, b 之间的最大边权即可。

记 distu\mathrm{dist}_u 表示距离 uu 最近的充电桩的距离，可以用多源点 dijkstra 求出。

但正常情况下可能要经过非充电桩的节点。考虑一个贪心策略：每次走到一个节点的时候，都去距离它最近的一个充电桩补满电量再回来。

由于起点与终点均为充电桩，若要经过原图上的一条边 (x,y,z)(x, y, z)，电池容量至少为 distx+z+disty\mathrm{dist}_x + z + \mathrm{dist}_y（至少要从充电桩走到其中一个端点，经过这条边，再从另外一个端点走到充电桩）。

故对于每条边 (x,y,z)(x, y, z)，使用 distx+z+disty\mathrm{dist}_x + z + \mathrm{dist}_y 代替它的边权。此时从 aa 走到 bb 的答案，即为 a,ba, b 之间所有简单路径上最大边权的最小值。