RainAir
My OI Blog
RainAir
「BZOJ5415」「NOI2018」归程

题目链接

题解

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

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/469
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望省选不要翻车,希望我还有脑子
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「BZOJ5415」「NOI2018」归程
题目链接 题解 首先我们尝试把不能被车经过的边删掉,得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边…
扫描二维码继续阅读
2019-02-07
文章归档