1 条题解
-
0

// 最短路径树+线段树 Dijkstra 算法 O(MlogN) #include<bits/stdc++.h> #define int long long #define pii pair<int,int> using namespace std; const int N=2e5+5; int idx=1,h[N],ne[N<<1],ww[N<<1],to[N<<1]; void add(int a,int b,int c){ to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx; } int n,m,q,u[N],v[N],w[N],L[N],R[N],eid[N]; int d1[N],dn[N],pre[N]; bool onpath[N]; void dijkstra(int s,int *d,int *p){ memset(d,0x3f,sizeof d1); d[s]=0; priority_queue<pii,vector<pii>,greater<pii> > q; q.emplace(0,s); while(!q.empty()){ auto [dd,u]=q.top(); q.pop(); if(dd!=d[u]) continue; for(int j=h[u]; j; j=ne[j]){ int v=to[j]; int w=ww[j]; if(d[v]>d[u]+w){ d[v]=d[u]+w; pre[v]=j/2; //记录v点的前驱边编号 if(!onpath[v]) p[v]=p[u]; //如果v点不在最短路径E上,v继承u的前缀 q.emplace(d[v],v); } } } } int cnt; struct segtree{ //线段树:区间为最短路径E的cnt条边 #define lc (u<<1) #define rc (u<<1|1) #define mid ((l+r)>>1) int mi[N<<2]; //节点维护不经过最短路径E的边区间[l,r]的最短路 void build(int u=1,int l=1,int r=cnt){ mi[u]=1e18; if(l==r) return; build(lc,l,mid),build(rc,mid+1,r); } void upd(int x,int y,int d,int u=1,int l=1,int r=cnt){ //区修 if(x>y) return; if(x<=l && r<=y) return mi[u]=min(mi[u],d),void(); //标记永久化 if(x<=mid) upd(x,y,d,lc,l,mid); if(y>mid) upd(x,y,d,rc,mid+1,r); } int ask(int x,int u=1,int l=1,int r=cnt){ //点查 if(l==r) return mi[u]; if(x<=mid) return min(mi[u],ask(x,lc,l,mid)); else return min(mi[u],ask(x,rc,mid+1,r)); } }T; signed main(){ cin>>n>>m>>q; for(int i=1; i<=m; i++){ cin>>u[i]>>v[i]>>w[i]; add(u[i],v[i],w[i]),add(v[i],u[i],w[i]); } dijkstra(n,dn,R); //预处理以n为根的最短路径树的前驱边pre L[1]=R[1]=0,onpath[1]=true; for(int p=1; p!=n;){ int i=pre[p]; //取出p点的前驱边i eid[i]=++cnt; //给最短路径E的边i编号 p=(u[i]==p)?v[i]:u[i]; //取出边i的右端点p L[p]=R[p]=cnt; //记录p点的左侧边的编号 onpath[p]=true; //记录p点在最短路径E上 } dijkstra(1,d1,L); dijkstra(n,dn,R); //预处理 d1,dn,L,R T.build(); for(int i=1; i<=m; i++)if(!eid[i]){ //如果i不是最短路径E的边 int a=u[i],b=v[i]; T.upd(L[a]+1,R[b],d1[a]+w[i]+dn[b]); //修改不经过最短路径E的边区间[l,r]的最短路 T.upd(L[b]+1,R[a],d1[b]+w[i]+dn[a]); } for(int i,x; q--;){ //q次询问 cin>>i>>x; if(eid[i]){ //i是最短路径E的边 if(x<=w[i]) cout<<d1[n]-w[i]+x; else cout<<min(d1[n]-w[i]+x, T.ask(eid[i])); } else{ if(x>=w[i]) cout<<d1[n]; else cout<<min({d1[n], d1[u[i]]+x+dn[v[i]], d1[v[i]]+x+dn[u[i]]}); } cout<<'\n'; } return 0; }
- 1
信息
- ID
- 12500
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者