ABC250Ex Trespassing Takahashi

[ABC250Ex] Trespassing Takahashi

link。

单次在关键点之间行走的路程不超过 ，忽略 的点，以两点间距离为边权，似乎是一个最小生成树状物。可以建出生成树，也可以将询问离线，按 升序逐个加边处理。

考虑只对可以直接抵达的关键点建边。关键在于如何找出边权。

先以 为源点跑多源最短路，并记录到每个点最近的源点 。

我们声称：对于一条从 到 的最短路径，**一定存在相邻两点 使得 **。

但很显然，由于只保留最近点中的一个，因此在有多个最近点时声称不一定成立。

此时对于 ，\2to3$ 至少一条不成立。

但由于只需要维护生成树，我们只需要保留其中一条边即可。

稍微证明一下。设“中心点”为 ，那么

• 对于 ， 与 有边。
• 对于 ， 与 有边，且边权大于上一类边。

感性理解，相邻点可以通过与 相接的方式形成正确的生成树。