我只会签到题.jpg。
显然可以使用二维线段树优化建图拿到一定的部分分，但是这并不优秀。
考虑从值域上来入手 dijkstra。看做是装置间的最短路顺带更新节点，那么我们可以写一个树套树来维护这一些待更新的点，因为 dist 是递增的，所以可以更新后删去这些点，然后就可以 \(n\log n\) 的空间通过这个题。
标签：dist,P5471,可以,更新,弹跳,NOI2019 From： https://www.cnblogs.com/Custlo/p/17520817.html
我只会签到题.jpg。
显然可以使用二维线段树优化建图拿到一定的部分分，但是这并不优秀。
考虑从值域上来入手 dijkstra。看做是装置间的最短路顺带更新节点，那么我们可以写一个树套树来维护这一些待更新的点，因为 dist 是递增的，所以可以更新后删去这些点，然后就可以 \(n\log n\) 的空间通过这个题。
标签：dist,P5471,可以,更新,弹跳,NOI2019 From： https://www.cnblogs.com/Custlo/p/17520817.html