线段树优化建图笔记
线段树优化建图笔记
问题
给定 个结点, 组边,第 组边从 $ P_i$ 向 到 这段点号区间中所有点连一条长度为 的边,求最短路。
线段树使用
首先线段树每一个区间节点都向这个节点的子区间节点连一条长度为零的边,叶子结点向这个长度为 的区间所表示的点连一条长度为零的边。
如果有一组边为从 号点向 这段区间连长度为 的边,则从 号点向区间节点 连一条长度为 的边,再从 这个点向区间节点 连一条长度为 的边,就完成了连边以及建图。
代码模板
在写了在写了
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's Blog!
评论