「BZOJ5415」「NOI2018」归程
题目链接题解首先我们尝试把不能被车经过的边删掉，得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序，用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就可以了。 但是这题目要求强制在线怎么办？我们可以使用可持久化并查集来维护这个东西。 可持久化并查集用可持久化线段树来实现，非常简单。代...
题目链接题解首先我们尝试把不能被车经过的边删掉，得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序，用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就可以了。 但是这题目要求强制在线怎么办？我们可以使用可持久化并查集来维护这个东西。 可持久化并查集用可持久化线段树来实现，非常简单。代...