Description

有 n 个点 \((n\leq 10^5)\)，三种操作：

  1 u v w 从u向v连一条权值为w的有向边 

2 u L R w 从u向[L,R]的所有结点连一条权值为w的有向边 

3 u L R w 从[L,R]的所有结点向u连一条权值为w的有向边

Solution

解锁了线段树优化建图的姿势。

感觉有点玄乎啊，优化建图实际上就是让线段树上的节点做一个中转，中转叶子节点到叶子节点的道路。

这老哥写的不错

注意边的空间要开大点！

Code

#include
    
     #include
     
      #include
      
       #include
       
        #define N 100005#define int long long#define min(A,B) ((A)<(B)?(A):(B))#define max(A,B) ((A)>(B)?(A):(B))#define swap(A,B) ((A)^=(B)^=(A)^=(B))int vis[N<<2];int root1,root2;int n,m,s,cnt,tot;int lch[N<<2],rch[N<<2];int dis[N<<2],head[N<<2];struct Edge{    int to,nxt,dis;}edge[N*20];struct Node{    int now,dis;    friend bool operator<(Node a,Node b){        return a.dis>b.dis;    }};void add(int x,int y,int z){    edge[++cnt].to=y;    edge[cnt].nxt=head[x];    edge[cnt].dis=z;    head[x]=cnt;}void build1(int &cur,int l,int r){    if(l==r){        cur=l;        return;    }    cur=++tot;    int mid=l+r>>1;    build1(lch[cur],l,mid);    build1(rch[cur],mid+1,r);    add(cur,lch[cur],0);add(cur,rch[cur],0);}void build2(int &cur,int l,int r){    if(l==r){        cur=l;        return;    }    cur=++tot;    int mid=l+r>>1;    build2(lch[cur],l,mid);    build2(rch[cur],mid+1,r);    add(lch[cur],cur,0);add(rch[cur],cur,0);}int getint(){    int x=0,f=0;char ch=getchar();    while(!isdigit(ch)) f|=ch=='-',ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    return f?-x:x;}void modify1(int cur,int l,int r,int ql,int qr,int x,int y){    if(ql<=l and r<=qr){        add(x,cur,y);        return;    }    int mid=l+r>>1;    if(ql<=mid)        modify1(lch[cur],l,mid,ql,qr,x,y);    if(mid
        
         >1;    if(ql<=mid)        modify2(lch[cur],l,mid,ql,qr,x,y);    if(mid
         
           pq; pq.push((Node){s,0}); while(pq.size()){ Node u=pq.top();pq.pop(); if(vis[u.now]) continue; vis[u.now]=1; for(int i=head[u.now];i;i=edge[i].nxt){ int to=edge[i].to; if(dis[to]>u.dis+edge[i].dis){ dis[to]=u.dis+edge[i].dis; pq.push((Node){to,dis[to]}); } } }}signed main(){ n=getint(),m=getint(),s=getint();tot=n; build1(root1,1,n);build2(root2,1,n); while(m--){ int opt=getint(); if(opt==1){ int a=getint(),b=getint(),c=getint(); add(a,b,c); } else if(opt==2){ int a=getint(),b=getint(),c=getint(),d=getint(); modify1(root1,1,n,b,c,a,d); } else{ int a=getint(),b=getint(),c=getint(),d=getint(); modify2(root2,1,n,b,c,a,d); } } for(int i=1;i<=(n<<2);i++) dis[i]=2e18; dis[s]=0; dijkstra(); for(int i=1;i<=n;i++){ if(dis[i]>=2e18) printf("-1 "); else printf("%I64d ",dis[i]); } return 0;}