AT_abc250_h [ABC250Ex] Trespassing Takahashi

推式子题

考虑如何求出任意一个点到离它最近的房子的距离？

有一个很巧妙的处理方法是，我们可以建一个超级源点，连向所有房子，权值设为 \(0\)，然后在新图上跑一个最短路，就能求出所有点到离它最近的房子的距离 \(dis\) 了。

然后考虑经过一条边的 \(t\) 最小是多少。比如说一条边从 \(i\) 连向 \(j\)。那么我们会从距离 \(i\) 最近的房子走向 \(i\)，然后经过 \(i\to j\) 这条边，最后走到距离 \(j\) 最近的房子。所以满足 \(t\ge dis_i+w_{i,j}+dis_j\)。

可以证明这个东西是对的。比如你现在求出了一条路径，你考虑你要从一个房子走向另一个房子，且中间没有其他房子，最大的部分会在中间出现，而且一定会出现。这个部分代表了从一个房子走向不同房子，由此不断推出是可行的。

考虑用这个东西作为新的点权，然后发现新的问题形如从 \(x\) 到 \(y\) 经过的路径上最大的边最小。所以用 kruscal 重构树维护就好了，也更简单的做法，考虑按照边权从小到大排序，询问也离线下来，用并查集处理就好了。