可以看出来难点在于建图，建完后一个堆优化dj就搞定
排除最朴素的循环建边，不难想到一种较为优化的方式：
将$(a,b)$的点向虚拟节点$p_1$连一条边权为0的边，再将$p_1$与$p_2$相连，边权为1，最后将$p_2$连到$(c,d)$边权为0。
但这还不是最优的方法，事实上，建图的过程完全可以用线段树优化。
由于建图要对区间进行操作，所以可以想到线段树（强行扯上关系）
建立A树与B树，A树的非叶子节点向父亲连边，B树的非叶子节点向儿子连边，边权为0;（两树的叶节点对应真实节点，其余为虚构点）
B树的叶节点向A树叶节点连边，
当进行区间连边操作时，找到区间在A线段树上的位置，把这部分向虚点连0权边，再连1权边到另一虚点，再连到B上，
没错，就是我们一开始考虑的小优化。
这里的线段树可以动态开点，注意跑dj时要用映射后的点编号。
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; #define pa pair<int,int> const int N=500005,M=3000005; int n,m,to[M<<3],nxt[M<<3],len[M<<3],head[M],tot,dis[M],s,v[M]; int ls[N<<2],rs[N<<2],type,key[N<<2],root1,root2; priority_queue<pa> q; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) {x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return x*f; } void add(int x,int y,int z) { to[++tot]=y; len[tot]=z; nxt[tot]=head[x]; head[x]=tot; } void build(int &k,int l,int r,int val) { k=++type; if(l==r) { if(val)key[l]=k; return ; } int mid=l+r>>1; build(ls[k],l,mid,val); build(rs[k],mid+1,r,val); if(val)add(ls[k],k,0),add(rs[k],k,0); else add(k,ls[k],0),add(k,rs[k],0); } void pre(int l,int r,int x,int y) { if(l==r) { add(y,x,0); return ; } int mid=l+r>>1; pre(l,mid,ls[x],ls[y]); pre(mid+1,r,rs[x],rs[y]); } void update(int S,int T,int l,int r,int x,int y,int val) { if(S<=l&&r<=T) { if(val)add(x,y,0); else add(y,x,0); return ; } int mid=l+r>>1; if(S<=mid)update(S,T,l,mid,ls[x],y,val); if(T>mid)update(S,T,mid+1,r,rs[x],y,val); } void link(int a,int b,int c,int d) { update(a,b,1,n,root1,++type,1); add(type,type+1,1); update(c,d,1,n,root2,++type,0); } void Dj(int st) { memset(dis,0x3f,sizeof(dis)); pa tmp=make_pair(0,key[st]); q.push(tmp); dis[key[st]]=0; while(!q.empty()) { int x=q.top().second; q.pop(); if(v[x])continue; v[x]=1; for(int i=head[x];i;i=nxt[i]) { if(dis[to[i]]>dis[x]+len[i]) { dis[to[i]]=dis[x]+len[i]; q.push(make_pair(-dis[to[i]],to[i])); } } } } int main() { n=read();m=read();s=read(); build(root1,1,n,1);build(root2,1,n,0); pre(1,n,root1,root2); for(int i=1;i<=m;i++) { int a=read(),b=read(),c=read(),d=read(); link(a,b,c,d);link(c,d,a,b); } Dj(s); for(int i=1;i<=n;i++) printf("%d\n",dis[key[i]]); return 0; }
[bzoj3073] Journeys 题解（线段树优化建图）
原文：https://www.cnblogs.com/Rorschach-XR/p/11178510.html