CF1253F Cheap Robot 做题记录

给定一张 $n$ 个点 $m$ 条边的无向图和一个正整数 $k$，边有边权表示机器人经过这条边消耗的电量，点 $1,2,3,\dots,k$ 为充电中心。机器人可以在充电中心免费充满电。

$q$ 组询问，每次给定两个节点 $s,t$，保证 $1\le s,t\le k$。你需要求解以下问题：

• 若有一个机器人从 $s$ 出发，它的电池容量至少为多少才能顺利到达 $t$？

$1\le n,m,q\le 3\times 10^5$

首先有一个敏锐的观察，发现 $1\le s,t\le k$ 很有用，这意味着有一个策略是每到达一个新的点就去最近的充电中心充一次电是不劣的。

观察出这个结论后，直接求出 $dis_u$ 表示 $u$ 到最近充电站的距离，那么对于一条路径 $E$，电池容量至少为 $\max\limits_{(u,v,w)\in E}\{dis_u+dis_v+w\}$。

那么做法就很显然了，求出 $dis_u$ 后把边 $(u,v,w)$ 变成 $(u,v,w+dis_u+dis_v)$，跑一遍 Kruskal 重构树即可。

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