題目鏈接：點擊查看

題目大意：給出 $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(线段树优化建图+最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。