CF786B Legacy 线段树优化建图 + spfa

短命女 2021-11-17 16:14 253阅读 0赞

Code:

#include<bits/stdc++.h>
    #define setIO(s) freopen(s".in","r",stdin) 
    #define maxn 4000000 
    #define inf 100000000000000  
    #define lson t[now].ls 
    #define rson t[now].rs   
    #define ll long long 
    using namespace std;    
    struct Data {
        int ls,rs,l,r; 
    }t[maxn];                                  
    queue<int>Q;  
    int n,q,s,rtin,rtout,cnt,edges; 
    int hd[maxn],to[maxn],nex[maxn];  
    ll val[maxn],dis[maxn];   
    int inq[maxn];      
    void addedge(int u,int v,ll c) {     
        nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;       
    }
    int newnode() {
        return ++cnt;   
    }
    namespace In {
        void build(int l,int r,int &now) {
            if(l==r) {
                now=l;               
                return; 
            }  
            int mid=(l+r)>>1;    
            now=newnode(), t[now].l=l, t[now].r=r; 
            build(l,mid,lson), addedge(now,lson,0); 
            if(r>mid) build(mid+1,r,rson), addedge(now,rson,0);               
        } 
        void Add(int l,int r,int now,int L,int R,int c) {
            if(l>=L&&r<=R) {
                addedge(c,now,0); 
                return; 
            }
            int mid=(l+r)>>1;  
            if(L<=mid) Add(l,mid,lson,L,R,c); 
            if(R>mid) Add(mid+1,r,rson,L,R,c);      
        }
    }; 
    namespace Out {
        void build(int l,int r,int &now) {
            if(l==r) {
                now=l;               
                return; 
            }  
            int mid=(l+r)>>1;    
            now=newnode(), t[now].l=l, t[now].r=r;     
            build(l,mid,lson), addedge(lson,now,0); 
            if(r>mid) build(mid+1,r,rson), addedge(rson,now,0);               
        }
        void Add(int l,int r,int now,int L,int R,int c) {
            if(l>=L&&r<=R) {
                addedge(now,c,0); 
                return; 
            }
            int mid=(l+r)>>1;  
            if(L<=mid) Add(l,mid,lson,L,R,c); 
            if(R>mid) Add(mid+1,r,rson,L,R,c);      
        }
    };  
    void Addedge(int l1,int r1,int l2,int r2,ll delta) { 
        int p1=newnode(), p2=newnode(); 
        addedge(p1,p2,delta);    
        Out::Add(1,n,rtout,l1,r1,p1);   
        In::Add(1,n,rtin,l2,r2,p2);      
    }
    void spfa() {
        for(int i=0;i<maxn;++i) dis[i]=inf;   
        Q.push(s), dis[s]=0,inq[s]=1; 
        while(!Q.empty()) {
            int u=Q.front(); Q.pop(); 
            inq[u]=0;   
            for(int i=hd[u];i;i=nex[i]) {
                int v=to[i]; 
                if(dis[v] > dis[u]+val[i]) {
                    dis[v]=dis[u]+val[i];
                    if(!inq[v]) 
                        Q.push(v), inq[v]=1; 
                }
            }
        }
    }
    int main() {
        // setIO("input"); 
        scanf("%d%d%d",&n,&q,&s);   
        cnt=n, In::build(1,n,rtin), Out::build(1,n,rtout);    
        for(int i=1;i<=q;++i) {
            int opt,l1,r1,l2,r2,w;      
            scanf("%d",&opt);  
            if(opt==1) scanf("%d%d",&l1,&l2),r1=l1,r2=l2;   
            if(opt==2) scanf("%d%d%d",&l1,&l2,&r2),r1=l1; 
            if(opt==3) scanf("%d%d%d",&l2,&l1,&r1),r2=l2;            
            scanf("%d",&w);   
            Addedge(l1,r1,l2,r2,1ll*w);        
        }  
        spfa();    
        for(int i=1;i<=n;++i) printf("%I64d ",dis[i]==inf?-1:dis[i]);     
        return 0; 
    }

转载于:https://www.cnblogs.com/guangheli/p/11226555.html