CodeForces - 787D - Legacy(线段树优化建图+最短路)

题目链接：点击查看

题目大意：给出 $n$ 个点和 $m$ 条边，现在需要求从 $st$ 开始到所有点的最短路是多少，$m$ 条边的给出方式如下：

$1uvw$：点 $u$ 向点 $v$ 连一条权值为 $w$ 的边

$2ulrw$：点 $u$ 向点 $i\in [l,r]$ 连一条权值为 $w$ 的边

$3ulrw$：点 $i\in [l,r]$ 向点 $u$ 连一条权值为 $w$ 的边

题目分析：区间操作不难想到线段树，对于这个题而言考虑拆点，建两棵对顶的线段树用来描述边的关系，形状如下：

按照上图建边，所有的边权都为 $0$，再考虑三种加边操作：

$u\to v$：树 $B$ 的叶子节点 $\to$ 树 $A$ 的叶子节点

$u\to [l,r]$：树 $B$ 的叶子节点 $\to$ 树 $A$ 中代表区间 $[l,r]$ 的节点

$[l,r]\to u$：树 $B$ 中代表区间 $[l,r]$ 的节点 $\to$ 树 $A$ 的叶子节点

然后跑最短路就好了

妙啊

代码：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const LL inf=0x3f3f3f3f3f3f3f3f; const int N=1e6+100; template<typename T> struct Dij {const static int N=1e6+100;const static int M=5e6+100;struct Edge{int to,next;T w;}edge[M];int head[N],cnt;//链式前向星 T d[N];bool vis[N];void addedge(int u,int v,T w){edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;}struct Node{int to;T w;Node(int TO,T W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;}};void Dijkstra(int st){priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,0x3f,sizeof(d));d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//扫描出所有边 {int v=edge[i].to;T w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}}}void init(){memset(head,-1,sizeof(head));cnt=0; } }; Dij<LL>t; int id=0; struct Seg {struct Node{int l,r,id;}tree[N<<2];void build(int k,int l,int r,bool flag)//flag=0:fa->son,flag=1:son->fa{tree[k].id=++id;tree[k].l=l,tree[k].r=r;if(l==r) return;int mid=(l+r)>>1;build(k<<1,l,mid,flag),build(k<<1|1,mid+1,r,flag);if(flag) t.addedge(tree[k<<1].id,tree[k].id,0),t.addedge(tree[k<<1|1].id,tree[k].id,0);else t.addedge(tree[k].id,tree[k<<1].id,0),t.addedge(tree[k].id,tree[k<<1|1].id,0);}void update(int k,int l,int r,int p,int w,bool flag)//flag=0:p->[l,r],flag=1:[l,r]->p{if(tree[k].l>r||tree[k].r<l) return;if(tree[k].l>=l&&tree[k].r<=r){if(flag) t.addedge(tree[k].id,p,w);else t.addedge(p,tree[k].id,w);return;}update(k<<1,l,r,p,w,flag),update(k<<1|1,l,r,p,w,flag);}int query(int k,int pos){if(tree[k].l==tree[k].r) return tree[k].id;int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) return query(k<<1,pos);else return query(k<<1|1,pos);}void dfs(int k){if(tree[k].l==tree[k].r){int p=tree[k].id;if(t.d[p]==inf) write(-1),putchar(' ');else write(t.d[p]),putchar(' ');return;}dfs(k<<1),dfs(k<<1|1);} }A,B; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);t.init();int n,m,st;read(n),read(m),read(st);A.build(1,1,n,0),B.build(1,1,n,1);for(int i=1;i<=n;i++)t.addedge(A.query(1,i),B.query(1,i),0);while(m--){int op;read(op);if(op==1)//u->v{int u,v,w;read(u),read(v),read(w);t.addedge(B.query(1,u),A.query(1,v),w);}else if(op==2)//p->[l,r]{int u,l,r,w;read(u),read(l),read(r),read(w);int p=B.query(1,u);A.update(1,l,r,p,w,0);}else if(op==3)//[l,r]->p{int u,l,r,w;read(u),read(l),read(r),read(w);int p=A.query(1,u);B.update(1,l,r,p,w,1);}}t.Dijkstra(A.query(1,st));B.dfs(1);return 0; }

总结

以上是生活随笔为你收集整理的CodeForces - 787D - Legacy(线段树优化建图+最短路)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。