upd on 2022.9.3：增加了对解法的描述。
Description
有一张有 (N) 个点，编号为 (1 – N) 的无向图。
做 (M) 次操作，每次操作给出三个正整数 (L,R,C)，对于每对 (≥L) 且 (≤R) 的整数对 ((S,T)) ，在 ((S,T)) 之间添加一条长度为 (C) 的边
完成操作后，找出操作后无向图的最短路。
- $ N,M\ \leq\ 10^5 $
Solution
线段树优化建图裸题。
看到区间向区间连边，显然暴力处理是 (O(MN)) 的，会时间超限。
那么可以想到处理区间问题的常用工具：线段树。
我们对整个区间建立线段树，把每个点分为入点和出点，构建出入树和出树。
在实现上述过程的时候，我们其实只要建一遍线段树。对于叶子结点，我们可以让两棵树共用，就不必再连边了。
那么对于一个点向一个区间连边，我们可以将其转化为这个点和区间在入树上分成的若干子区间对应的节点连边。
区间向点连边同理，将出树上该区间分成的子区间分别向这个点连边。
题目要求我们区间向区间连边，这个时候我们可以新建一个节点，将出树区间向这个节点连边，这个点再向入树区间连边，就可以了。
然后剩下的就是在建好的图上跑最短路板子，我用的堆优化的 Dijkstra，就不赘述了。
细节可以看代码注释。
Code
#include
#define gc() getchar()
using namespace std;
typedef long long ll;
template void rd(T &x){
T f=1;x=0;char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<>1;
in[o]=++tot,out[o]=++tot;// 存储 o 代表的区间对应的图中节点
build(o<=l&&t[o].r>1;
// 递归加边
if(lmid)addedge(o<a.w;}
};
priority_queueq;
inline void dij(){
memset(d,0x3f,sizeof(d));
d[1]=0;q.push(pq(1,0));
while(!q.empty()){
pq x=q.top();q.pop();
int u=x.v;if(vis[u])continue;
vis[u]=1;
for(int i=hd[u];i;i=g[i].nxt){
int v=g[i].v,w=g[i].w;
if(d[v]>d[u]+w)d[v]=d[u]+w,q.push(pq(v,d[v]));
}
}
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
rd(n),rd(m);tot=n;// tot 从 n 开始，避免与叶子节点重复
build(1,1,n);// 别忘了建树
for(int i=1;i
(by\ sysong)
(2022.8.30)
Original: https://www.cnblogs.com/sysong2006/p/16641279.html
Author: _sysong
Title: 题解 AT5635 Shortest Path on a Line（线段树优化建图）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587549/
转载文章受原作者版权保护。转载请注明原作者出处！