题解 CF786B 【Legacy】

**题意分析** 这一题最主要是有三种操作：1.进行单点与单点连有向边 2.进行单点与区间连有向边 3.进行区间与单点连有向边。然后求最短路。 这一道题，最大的难点不在最短路（直接套Dij模板），而在于如何连边。如果按照题意模拟，一个点到区间中的一个点进行连接，其复杂度在最坏情况下会达到O(n*n)（即每一个点向整个区间连边），任何一个有常识的人都能看出这样一定会TLE的。 对于我们来说，最大的难点就是要解决单点与区间之间的操作。一看到区间，我们首先想到的就是前缀和、差分、ST表、树状数组、线段树。其实，这一题本质上就是一道特殊的线段树题。 那么怎么把一个线段树放到图里面呢？这里我们发现，如果只建立一个线段树是很难实现的，那么我们一不做二不休，就建立两个线段树。 ```cpp int n,q,s,cnt,treeOut[MAXN<<2],treeIn[MAXN<<2]; ``` 我们用treeOut专门处理由线段树向外连边，其效果如图所示：  有图可见，我们在线段树内建立了多条有向虚边。且treeIn和treeOut的线段树虚边的方向是相反的，如图则是treeIn：  那么为什么要这样建立虚边，这里就用一张图来演示一下：  由图可知，错误的连边会导致访问的区间出错。比如在这张错误的图中，一个只能访问[mid+1,right]的连边却访问到了[left,right]。 ***代码*** ```cpp static vector<pair<int,int>> edge[MAXN*10]; ``` 我们使用vector建图，相比于链表来说会方便一些（2s,STL不怂）。 ```cpp inline void build(int k,int l,int r){ if(l==r){ treeOut[k]=l; treeIn[k]=l; return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); treeOut[k]=++cnt; treeIn[k]=++cnt; edge[treeOut[k<<1]].push_back make(treeOut[k],0); edge[treeOut[k<<1|1]].push_back make(treeOut[k],0); edge[treeIn[k]].push_back make(treeIn[k<<1],0); edge[treeIn[k]].push_back make(treeIn[k<<1|1],0); } inline void updateIn(int k,int l,int r,int L,int R,int from,int cost){ if(L<=l&&r<=R){ edge[from].push_back(make(treeIn[k],cost)); return ; } int mid=(l+r)>>1; if(L<=mid){ updateIn(k<<1,l,mid,L,R,from,cost); } if(mid<R){ updateIn(k<<1|1,mid+1,r,L,R,from,cost); } } inline void updateOut(int k,int l,int r,int L,int R,int from,int cost){ if(L<=l&&r<=R){ edge[treeOut[k]].push_back(make(from,cost)); return ; } int mid=(l+r)>>1; if(L<=mid){ updateOut(k<<1,l,mid,L,R,from,cost); } if(mid<R){ updateOut(k<<1|1,mid+1,r,L,R,from,cost); } } ``` 常规的建树操作，最大的区别是要在建树的时候还要进行建图操作。树的每一个节点储存着该区间在图中的编号。需要注意的是，当该区间就是一个点时,树中储存的就是改点的便后，即： ```cpp if(l==r){ treeOut[k]=l; treeIn[k]=l; return; } ``` 在这道题中，update的作用不在于修改树中的值，而是在于建图，这是他与一般线段树的区别。 以下是全部代码： ```cpp #include<bits/stdc++.h> #define ini(x,y) memset(x,y,sizeof(x)) #define all(x) x.begin(),x.end() #define F(x,y,z) for(int x=y;x<=z;++x) #define D(x,y,z) for(int x=y;x>=z;--x) #define cint const int& using namespace std; /*请以C++11提交,Develop By ZhangXinjie（江南柚子）*/ const int MAXN=static_cast<int>(1e5)+100; const long long INF=0x3f3f3f3f3f3f3f3f; const int oo=0x3f3f3f3f; #define int long long inline int read(){ int x = 0, y = 1, c = getchar(); while (c>'9' || c<'0') { if (c == '-')y = -1; c = getchar(); } while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * y; } #define make(x,y) (make_pair(x,y)) #define to first #define v second static vector<pair<int,int>> edge[MAXN*10]; static int n,q,s,cnt,treeOut[MAXN<<2],treeIn[MAXN<<2]; inline void build(int k,int l,int r){ if(l==r){ treeOut[k]=l; treeIn[k]=l; return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); treeOut[k]=++cnt; treeIn[k]=++cnt; edge[treeOut[k<<1]].push_back make(treeOut[k],0); edge[treeOut[k<<1|1]].push_back make(treeOut[k],0); edge[treeIn[k]].push_back make(treeIn[k<<1],0); edge[treeIn[k]].push_back make(treeIn[k<<1|1],0); } inline void updateIn(int k,int l,int r,int L,int R,int from,int cost){ if(L<=l&&r<=R){ edge[from].push_back(make(treeIn[k],cost)); return ; } int mid=(l+r)>>1; if(L<=mid){ updateIn(k<<1,l,mid,L,R,from,cost); } if(mid<R){ updateIn(k<<1|1,mid+1,r,L,R,from,cost); } } inline void updateOut(int k,int l,int r,int L,int R,int from,int cost){ if(L<=l&&r<=R){ edge[treeOut[k]].push_back(make(from,cost)); return ; } int mid=(l+r)>>1; if(L<=mid){ updateOut(k<<1,l,mid,L,R,from,cost); } if(mid<R){ updateOut(k<<1|1,mid+1,r,L,R,from,cost); } } struct heapnode{ int pos,dis; bool operator<(heapnode right)const{ return dis>right.dis; } }; static int dis[MAXN*10]; static priority_queue<heapnode>heap; inline void dij(){ ini(dis,0x3f); dis[s]=0; heapnode tmp; tmp.dis=0; tmp.pos=s; heap.push(tmp); while(!heap.empty()){ heapnode now=heap.top(); heap.pop(); if(dis[now.pos]!=now.dis){ continue; } for(auto &i:edge[now.pos]){ if(i.to==0){ continue; } if(i.v+now.dis<dis[i.to]){ dis[i.to]=i.v+now.dis; tmp.pos=i.to; tmp.dis=dis[i.to]; heap.push(tmp); } } } } signed main(){ n=read(); q=read(); s=read(); cnt=n; build(1,1,n); F(i,1,q){ int com=read(); if(com==1){ int from=read(),to=read(),v=read(); edge[from].push_back(make(to,v)); }else{ if(com==2){ int from=read(),l=read(),r=read(),v=read(); updateIn(1,1,n,l,r,from,v); }else{ int from=read(),l=read(),r=read(),v=read(); updateOut(1,1,n,l,r,from,v); } } } dij(); F(i,1,n){ printf("%lld ",(dis[i]==INF)?-1:dis[i]); } return 0; } ``` 至于为什么使用dij算法而不用SPFA，因为 ``` 1<=w<=10^9 ``` 以及NOI2018D1T1的血的教训。 还有，记得使用long long