Codeforces 786 B. Legacy

题目链接：http://codeforces.com/contest/786/problem/B
　　典型线段树优化连边，线段树上的每一个点表示这个区间的所有点，然后边数就被优化为了至多${nlogn}$条，注意要区分$2$,$3$操作(建两棵线段树)，然后最短路即可。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 using namespace std;
  9 #define maxn 1001000
 10 #define llg long long
 11 #define INC 300000
 12 #define SIZE 2000000 
 13 #define inf (llg)1e18
 14 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 15 llg n,dis[maxn],dl[SIZE+10],head,tail,pos[maxn];
 16 bool bj[maxn];
 17 
 18 vector<llg>a[maxn],val[maxn];
 19 
 20 inline int getint()
 21 {
 22        int w=0,q=0; char c=getchar();
 23        while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
 24        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
 25 }
 26 
 27 void link(llg x,llg y,llg z) {a[x].push_back(y),val[x].push_back(z);}
 28 
 29 void build(llg o,llg l,llg r)
 30 {
 31     if (l==r)
 32     {
 33         pos[l]=o;
 34         return ;
 35     }
 36     llg mid=(l+r)>>1,lc=o<<1,rc=o<<1|1;
 37     build(lc,l,mid); build(rc,mid+1,r);
 38 }
 39 
 40 void find(llg o,llg l,llg r,llg L,llg R,llg val,bool f,llg v)
 41 {
 42     if (l>=L && r<=R)
 43     {
 44         if (f) link(pos[v],o,val);else link(o+INC,pos[v],val);
 45         return ;
 46     }
 47     llg mid=(l+r)>>1,lc=o<<1,rc=o<<1|1;
 48     if (mid>=L) find(lc,l,mid,L,R,val,f,v);
 49     if (mid<R) find(rc,mid+1,r,L,R,val,f,v);
 50 }
 51 
 52 
 53 
 54 void link_fa(llg o,llg l,llg r)
 55 {
 56     for (llg i=l;i<=r;i++) link(o,pos[i],0),link(pos[i],o+INC,0);
 57     if (l==r) return ;
 58     llg mid=(l+r)>>1,lc=o<<1,rc=o<<1|1;
 59     link_fa(lc,l,mid); link_fa(rc,mid+1,r);
 60 }
 61 
 62 void init()
 63 {
 64     llg t,v,u,w,l,r,s,q;
 65     n=getint(),q=getint(),s=getint();
 66     build(1,1,n);
 67     for (llg i=1;i<=q;i++)
 68     {
 69         t=getint();
 70         if (t==1) 
 71         {
 72             v=getint(),u=getint(),w=getint();
 73             link(pos[v],pos[u],w);
 74         }
 75         if (t==2)
 76         {
 77             v=getint(),l=getint(),r=getint(),w=getint();
 78             find(1,1,n,l,r,w,1,v);
 79         }
 80         if (t==3)
 81         {
 82             v=getint(),l=getint(),r=getint(),w=getint();
 83             find(1,1,n,l,r,w,0,v);
 84         }
 85     }
 86     link_fa(1,1,n);
 87     for (llg i=1;i<maxn;i++) dis[i]=inf;
 88     dis[pos[s]]=0;
 89     dl[1]=pos[s],head=0,tail=1;
 90 }
 91 
 92 void spfa()
 93 {
 94     llg w,x,v;
 95     do
 96     {
 97         head%=SIZE; head++;
 98         x=dl[head]; w=a[x].size(); bj[x]=0;
 99         for (llg i=0;i<w;i++)
100         {
101             v=a[x][i];
102             if (dis[v]>dis[x]+val[x][i])
103             {
104                 dis[v]=dis[x]+val[x][i];
105                 if (!bj[v])
106                 {
107                     bj[v]=1;
108                     tail%=SIZE; tail++;
109                     dl[tail]=v;
110                 }
111             }
112         }
113     }while (head!=tail);
114 }
115 
116 int main()
117 {
118     yyj("graph");
119     init();
120     spfa();
121     for (llg i=1;i<=n;i++) if (dis[pos[i]]==inf) printf("-1 "); else printf("%lld ",dis[pos[i]]);
122     return 0;
123 }