1253F

题意 给定一个图，走过一条边的花费为权值，其中有 \(k\) 个充电点。 你需要确定一个电量的上限，使得满足从 \(a\) 走到 \(b\)。 Sol 先对于每个点求出她走到充电点最近的距离，用 \(dij\) 随便跑跑。 考虑从 \(a \to b\) 一条边的贡献。设当前的电量上限为 \(c\) ......

Cheap Robot 题面翻译 给你一张 \(N\) 个点的带权无向连通图，其中结点 \(1,2,…,k\) 为充电中心。 一个机器人在图中行走，假设机器人的电池容量为 \(c\)，则任何时刻，机器人的电量 \(x\) 都必须满足 \(0\le x\le c\)。如果机器人沿着一条边权为 \(w\ ......