线段树优化建图 || CF786B Legacy

比眉伴天荒 2021-10-26 15:32 219阅读 0赞

题面：[786B - Legacy][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
      2 #include<cstring>
      3 #include<iostream>
      4 #include<queue>
      5 #define ll long long
      6 using namespace std;
      7 inline ll rd(){
      8     ll x=0,f=1;char c=getchar();
      9     while(c<'0'||c>'9'){
         if(c=='-')f=-1; c=getchar();}
     10     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
     11     return f*x;
     12 }
     13 const int maxn=(1e5)+50,maxq=maxn;
     14 const ll inf=1ll<<60;
     15 int N,S,Q,o,v,u,ql,qr,num_edge=0,edge_head[maxn*15];
     16 int tr[maxn*15][3],cnt;
     17 ll w,Dis[maxn*15];
     18 bool vis[maxn*15];
     19 struct Num_{
     20     int id;ll dis;
     21     bool operator < (const Num_&a) const{
     22         return a.dis<dis;
     23     }
     24 }e;
     25 priority_queue<Num_>pri;
     26 struct Edge{ int to,nx; ll dis; }edge[maxn*40];
     27 inline void Add_edge(int from,int to,int dis){
     28     edge[++num_edge].nx=edge_head[from];
     29     edge[num_edge].to=to;
     30     edge[num_edge].dis=dis;
     31     edge_head[from]=num_edge;
     32     return;
     33 }
     34 void Build(int x,int l,int r){
     35     if(l==r){
     36         tr[x][0]=tr[x][1]=l;
     37         return;
     38     }
     39     int m=(l+r)>>1;
     40     tr[x][0]=++cnt; tr[x][1]=++cnt;
     41     Build(x<<1,l,m); Build(x<<1|1,m+1,r);
     42     Add_edge(tr[x][0],tr[x<<1][0],0);
     43     Add_edge(tr[x][0],tr[x<<1|1][0],0);
     44     Add_edge(tr[x<<1][1],tr[x][1],0);
     45     Add_edge(tr[x<<1|1][1],tr[x][1],0);
     46     return;
     47 }
     48 void Update(int x,int l,int r,int ql,int qr,int u,int val,int op){
     49     if(ql<=l&&r<=qr){
     50         if(op==0) Add_edge(u,tr[x][0],val);
     51         else Add_edge(tr[x][1],u,val);
     52         return;
     53     }
     54     int m=(l+r)>>1;
     55     if(ql<=m)Update(x<<1,l,m,ql,qr,u,val,op);
     56     if(qr>m)Update(x<<1|1,m+1,r,ql,qr,u,val,op);
     57     return;
     58 }
     59 inline void Dijkstra(int s){
     60     for(int i=1;i<=cnt;i++)Dis[i]=inf;
     61     Dis[s]=0;
     62     e.id=s;e.dis=0;
     63     pri.push(e);
     64     while(!pri.empty()){
     65         int x=(pri.top()).id;
     66         pri.pop();
     67         if(vis[x])continue;
     68         vis[x]=1;
     69         for(int i=edge_head[x];i;i=edge[i].nx){
     70             int y=edge[i].to;
     71             if(Dis[x]+edge[i].dis<Dis[y]){
     72                 Dis[y]=Dis[x]+edge[i].dis;
     73                 e.id=y;e.dis=Dis[y];
     74                 pri.push(e);
     75             }
     76         }
     77     }
     78     return;
     79 }
     80 int main(){
     81     N=rd();Q=rd();S=rd();
     82     cnt=N;
     83     Build(1,1,N);
     84     while(Q--){
     85         o=rd();
     86         if(o==1){
     87             v=rd();u=rd();w=rd();
     88             Add_edge(v,u,w);
     89         }
     90         else {
     91             v=rd();ql=rd();qr=rd();w=rd();
     92             if(o==2)
     93                 Update(1,1,N,ql,qr,v,w,0);
     94             else//o==3
     95                 Update(1,1,N,ql,qr,v,w,1);
     96         }
     97     }
     98     Dijkstra(S);
     99     for(int i=1;i<=N;i++)
    100         if(Dis[i]!=inf)printf("%lld ",Dis[i]);
    101         else printf("-1 ");
    102     return 0;
    103 }

邻接表建图版

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
      2 #include<cstring>
      3 #include<iostream>
      4 #include<queue>
      5 #define make(a,b) (make_pair(a,b))
      6 #define ll long long
      7 using namespace std;
      8 inline ll rd(){
      9     ll x=0,f=1;char c=getchar();
     10     while(c<'0'||c>'9'){
         if(c=='-')f=-1; c=getchar();}
     11     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
     12     return f*x;
     13 }
     14 const int maxn=(1e5)+50,maxq=maxn;
     15 const ll inf=1ll<<60;
     16 int N,Q,S,trIn[maxn<<2],trOut[maxn<<2];
     17 int u,v,ql,qr,o,cnt;
     18 bool vis[maxn<<3];
     19 vector<pair<int,ll> >edge[maxn<<3];//to,val
     20 ll w,Dis[maxn<<3];
     21 struct Num_{
     22     ll dis;
     23     int id;
     24     bool operator < (const Num_&a) const {
     25         return a.dis<dis;
     26     }
     27 }b;
     28 priority_queue<Num_>pri;
     29 void Build(int x,int l,int r){
     30     if(l==r){
     31         trIn[x]=l;
     32         trOut[x]=l;
     33         return;
     34     }
     35     int mid=(l+r)>>1;
     36     trIn[x]=++cnt;trOut[x]=++cnt;
     37     Build(x<<1,l,mid);Build(x<<1|1,mid+1,r);
     38     edge[trIn[x]].push_back(make(trIn[x<<1],0));
     39     edge[trIn[x]].push_back(make(trIn[x<<1|1],0));
     40     edge[trOut[x<<1]].push_back(make(trOut[x],0));
     41     edge[trOut[x<<1|1]].push_back(make(trOut[x],0));
     42     return;
     43 }
     44 void Update(int x,int l,int r,int ql,int qr,int u,int val,int o){
     45     if(ql<=l&&r<=qr){
     46         if(o==2)//In
     47             edge[u].push_back(make(trIn[x],val));
     48         else//Out
     49             edge[trOut[x]].push_back(make(u,val));
     50         return;
     51     }
     52     int mid=(l+r)>>1;
     53     if(ql<=mid)Update(x<<1,l,mid,ql,qr,u,val,o);
     54     if(qr>mid)Update(x<<1|1,mid+1,r,ql,qr,u,val,o);
     55     return;
     56 }
     57 inline void Dijkstra(int s){
     58     for(int i=1;i<=cnt;i++)Dis[i]=inf;
     59     Dis[s]=0;
     60     b.dis=0;b.id=s;
     61     pri.push(b);
     62     while(!pri.empty()){
     63         int x=(pri.top()).id;
     64         pri.pop();
     65         if(vis[x])continue;
     66         vis[x]=1;
     67         int toi=edge[x].size();
     68         for(int i=0;i<toi;i++){
     69             int y=edge[x][i].first;
     70             if(Dis[y]>Dis[x]+edge[x][i].second){
     71                 Dis[y]=Dis[x]+edge[x][i].second;
     72                 b.id=y;b.dis=Dis[y];
     73                 pri.push(b);
     74             }
     75         }
     76     }
     77     return;
     78 }
     79 int main(){
     80     N=rd();Q=rd();S=rd();
     81     cnt=N;
     82     Build(1,1,N);
     83     while(Q--){
     84         o=rd();
     85         if(o==1){
     86             v=rd();u=rd();w=rd();
     87             edge[v].push_back(make(u,w));
     88         }
     89         else if(o==2){
     90             v=rd();ql=rd();
     91             qr=rd();w=rd();
     92             Update(1,1,N,ql,qr,v,w,2);
     93         }
     94         else {
         //o==3
     95             v=rd();ql=rd();
     96             qr=rd();w=rd();
     97             Update(1,1,N,ql,qr,v,w,3);
     98         }
     99     }
    100     Dijkstra(S);
    101     for(int i=1;i<=N;i++){
    102         if(Dis[i]!=inf) printf("%lld ",Dis[i]);
    103         else printf("-1 ");
    104     }
    105     return 0;
    106 }

Vector建图版

--------------------

By:AlenaNuna

转载于:https://www.cnblogs.com/AlenaNuna/p/11300895.html

[786B - Legacy]: http://codeforces.com/problemset/problem/786/B
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/82b6d2c283934116b78eff60d1aea2d1.png