图论专题新学的知识点有点太多了，还是新开一篇比较好。
数据结构优化建图
reference：常见优化建图技巧。
考虑一个题：CF786B。思考如何维护单点/区间向单点/区间连边：
-
点对点。直接连就行。
-
点对区间。开一颗线段树，每个节点代表一段区间，父亲向儿子连权为 \(0\) 的边。点对区间连边时直接向 \(\log n\) 个代表点连边即可。
-
区间对点。与上边类似，开一颗线段树，儿子向父亲连权为 \(0\) 的边。从 \(\log n\) 个代表点连出去即可。
-
区间对区间。新建一个虚点为这两个区间做一个中转即可。
回到这个题。这个题需要同时维护点对点，区间对点，点对区间连边，求最短路。开两颗线段树，父亲向儿子连边的是第一颗，儿子向父亲连边的是第二颗。
-
点对点，从第二颗的叶子连到第一颗的叶子。
-
点对区间，从第二颗的叶子连到第一颗的区间。
-
区间对点，从第二颗的区间连到第一颗的叶子。
正确性显然。最短路直接从第二颗线段树上 \(s\) 对应的叶子开始跑即可。注意到此时两颗线段树上对应叶子节点间都要互连权为 \(0\) 的边，因为他们代表的是同一个点。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mk make_pair
#define fi first
#define se second
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
typedef pair<int,int>pii;
const int inf=1e18,N=5e5;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,w,nxt;
}e[4000005];
int tot,head[1000005];
void add(int u,int v,int w){
e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}
int lf[100005];
void build(int l,int r,int p){
if(l==r){lf[l]=p;return;}
int mid=(l+r)>>1;
add(p,ls(p),0),add(p,rs(p),0);
add(ls(p)+N,p+N,0),add(rs(p)+N,p+N,0);
build(l,mid,ls(p));build(mid+1,r,rs(p));
}
void solve(int l,int r,int p,int op,int u,int L,int R,int w){
if(L<=l&&r<=R){
if(op==2)add(lf[u]+N,p,w);
else add(p+N,lf[u],w);
return;
}
int mid=(l+r)>>1;
if(L<=mid)solve(l,mid,ls(p),op,u,L,R,w);
if(R>mid)solve(mid+1,r,rs(p),op,u,L,R,w);
}
int d[1000005],vis[1000005];
void dijkstra(int s){
priority_queue<pii,vector<pii>,greater<pii> >q;
for(int i=1;i<=N*2;i++)d[i]=inf,vis[i]=0;
d[s]=0;q.push(mk(d[s],s));
while(!q.empty()){
int u=q.top().se;q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(d[u]+w<d[v])d[v]=d[u]+w,q.push(mk(d[v],v));
}
}
}
signed main(){
int n=read(),m=read(),s=read();build(1,n,1);
for(int i=1;i<=n;i++)add(lf[i],lf[i]+N,0),add(lf[i]+N,lf[i],0);
while(m--){
int op=read();
if(op==1){
int u=read(),v=read(),w=read();
add(lf[u]+N,lf[v],w);
}
else{
int u=read(),l=read(),r=read(),w=read();
solve(1,n,1,op,u,l,r,w);
}
}
dijkstra(lf[s]+N);
for(int i=1;i<=n;i++)printf("%lld ",((d[lf[i]]>=inf)?-1:d[lf[i]]));
return 0;
}
还有一些，学会了再补。