萌新求调线段树优化建图

#include <bits/stdc++.h>
using namespace std;
int n,m,s;
int a,b,c,d;
const int N=3e6+5;
int head[N],ecnt;
struct edge{
    int v,nxt,w;    
}e[N];
void add(int u,int v,int w){
    e[ecnt].v=v;
    e[ecnt].w=w;
    e[ecnt].nxt=head[u];
    head[u]=ecnt++;
}

int lc[N],rc[N];
int cnt;
int rt,rt2;
void build(int &p,int l,int r){
    if(l==r){
        p=l;
        return ;
    }
    p=++cnt;
    int m=l+r>>1;
    build(lc[p],l,m);
    build(rc[p],m+1,r);
    add(p,lc[p],0); add(p,rc[p],0);
} 
void build2(int &p,int l,int r){
    if(l==r){
        p=l;
        return ;
    }
    p=++cnt;
    int m=l+r>>1;
    build2(lc[p],l,m);
    build2(rc[p],m+1,r);
    add(lc[p],p,0); add(rc[p],p,0);
}

void upd(int p,int l,int r,int q,int L,int R,int op){
    if(L<=l&&r<=R){
        if(op==1) add(p,q,0);
        else add(q,p,0);
        return ;
    }
    int m=l+r>>1;
    if(L<=m) upd(lc[p],l,m,q,L,R,op);
    if(R>=m+1) upd(rc[p],m+1,r,q,L,R,op);
}
void add_edge(int a,int b,int c,int d){
    int q=++cnt,q2=++cnt;
    upd(rt,1,n,q,a,b,1);
    upd(rt2,1,n,q2,c,d,2);
    add(q,q2,1);
}

int dis[N];
void spfa(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i+1;i=e[i].nxt){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push(v);
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    memset(head,-1,sizeof(head));
    cnt=n;
    build(rt,1,n); build2(rt2,1,n);
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c>>d;
        add_edge(a,b,c,d);
        add_edge(c,d,a,b);
    } 
    spfa(s);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<endl;
    }
}