Codeforces，luogu。如果我们从走的路径长短出发去思考问题会很困难。因为目的是走到终点，求出容量，这一过程中只有行与不行之分。从此出发，对于当前点\(u\)，可以通过走到最近的一个充电站再走回来以增加当前电量。因此我们要处理每个点到最近充电站的距离。距离可以通过建一个超级源

首先建立一个超级点\(S\)，对于每一个可以充电的点\(u\)都建立一条从\(S\tou\)的边权为\(0\)的有向边。从这个超级点\(S\)开始跑一遍最短路算法，就可以得到每一个点\(u\)至少需要花费多少的电量才可以走到一个充电点。令\(D_i\)表示\(i\)号点最少花费多少可以到一个

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

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