首页 > 其他分享 >CF1163F Indecisive Taxi Fee

CF1163F Indecisive Taxi Fee

时间:2022-10-20 20:55:57浏览次数:90  
标签:Taxi dis1 Fee int CF1163F 短路 tr MAXN dis

题意

给定一张无向图,每次询问为更改一条边的边权后,从 \(1\) 到 \(n\) 的最短路。

Solution

首先考虑有哪些情况。如果原图中 \(1\to n\) 的最短路为路径 \(P\),其上第 \(i\) 个点为 \(P_i\)。

  1. 删去的边在 \(P\) 上,且边权变大;
  2. 删去的边在 \(P\) 上,且边权变小;
  3. 删去的边不在 \(P\) 上,且边权变大;
  4. 删去的边不在 \(P\) 上,且边权变小。

现在为了解决上面的情况,不难想到先求出 \(1\) 到任意点的最短路 \(dis_{1,x}\) 和 \(n\) 到任意点的最短路 \(dis_{x,n}\)。现在我们分情况解决上面的问题:

  1. 显然当前最优的仍然是路径 \(P\);
  2. 显然当前最优的仍然是路径 \(P\);
  3. 显然有可能代替 \(P\) 的路径是经过更改的边的,所以让原答案与 \(\min(dis_{1,u}+w+dis_{v,n},dis_{1,v}+w+dis_{u,n})\) 取 \(\min\) 即可。

现在最麻烦的部分就是在情况 \(1\)。

考虑对于情况 \(1\),我们对路径的优化。不难想到,如果新的路径 \(P'\not ={P}\),那么二者必然共享一段前缀和后缀。且中间跨越了那条变大的边。

Proof 考虑如果中间脱离路径 $P$ 多次,那么除了跨越修改边之外的跨越,都会劣于从 $P$ 上过,否则就不满足原图最短路的性质。所以最多跨越一次且中间跨越了修改边。

人类智慧!考虑对于不在 \(P\) 上的每条边,我们都可以找到经过这条边的最短路与 \(P\) 的公共前缀结束位置 \(L\) 和与 \(P\) 的公共后缀的开始位置 \(R\)。这个东西的求法,就是先求出路径 \(P\),然后在跑从 \(1\) 开始的最短路的时候,更新 \(L\),然后在从 \(n\) 开始跑最短路的时候更新 \(R\)。

那么知道了这个有什么用呢?继续人类智慧!我们把 \(P\) 拉出来摊成一条线段,建一棵线段树,然后对于路径外每一条边,可以在线段树上区间 \([L,R]\) 上打标记,然后此时线段树的意义就是,标记永久化之后,每个叶子节点的值就是不经过这条边的最短路的长度。

这就是我们想要的。考虑对于情况 \(1\),我们实际上答案是在 原最短路加上边权的变化量 和 不过修改边的最短路 中取最小的那条。

细节:

  • 把最短路展开之后,线段树下标要重编号,并且是对边重编号的。以靠近 \(1\) 的点为代表;

好像有双倍经验 P3238

Code

// Problem: CF1163F Indecisive Taxi Fee
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1163F
// Memory Limit: 3000 MB
// Time Limit: 500000 ms

#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define siz(a) (int)a.size()
#define pb emplace_back
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
#define int long long
using namespace std;
const int MAXN=2e5+10;
struct Tree{int l,r,inc;}tr[MAXN<<2];
#define ls i<<1
#define rs i<<1|1
void build(int i,int l,int r){
	tr[i].l=l;tr[i].r=r;tr[i].inc=INF;
	if(l==r) return;int mid=(l+r)>>1;
	build(ls,l,mid);build(rs,mid+1,r);
}
void upd(int i,int l,int r,int v){
	if(l>r) return;
	if(tr[i].l==l&&tr[i].r==r){tr[i].inc=min(tr[i].inc,v);return;}
	int mid=(tr[i].l+tr[i].r)>>1;
	if(r<=mid) upd(ls,l,r,v);else if(l>mid) upd(rs,l,r,v);
	else upd(ls,l,mid,v),upd(rs,mid+1,r,v);
}
int ask(int i,int x){
	if(tr[i].l==tr[i].r) return tr[i].inc;
	int mid=(tr[i].l+tr[i].r)>>1;
	int ret=tr[i].inc;
	if(x<=mid) ret=min(ret,ask(ls,x));
	else ret=min(ret,ask(rs,x));
	return ret;
}
struct Edge{int to,w,id;};
vector<Edge> e[MAXN];
int u[MAXN],v[MAXN],w[MAXN];
int dis1[MAXN],disn[MAXN],L[MAXN],R[MAXN];
int pre1[MAXN],pren[MAXN];
vector<int> suf1[MAXN],sufn[MAXN];
struct node{
	int x,dis;
	bool friend operator<(node a,node b){
		return a.dis>b.dis;
	}
};
priority_queue<node> q;
int num[MAXN],onp[MAXN];
void solve(){
	int n,m,Q;cin>>n>>m>>Q;
	rep(i,1,m){
		cin>>u[i]>>v[i]>>w[i];
		e[u[i]].pb(Edge{v[i],w[i],i});
		e[v[i]].pb(Edge{u[i],w[i],i});
	}
	memset(dis1,0x3f,sizeof(dis1));
	memset(disn,0x3f,sizeof(disn));
	q.push(node{1,0});dis1[1]=0;
	while(!q.empty()){
		node now=q.top();q.pop();
		if(dis1[now.x]<now.dis) continue;
		for(auto s:e[now.x]){
			node nxt=node{s.to,now.dis+s.w};
			if(dis1[nxt.x]>nxt.dis){
				pre1[nxt.x]=now.x;
				dis1[nxt.x]=nxt.dis;
				q.push(nxt);
			}
		}
	}
	q.push(node{n,0});disn[n]=0;
	while(!q.empty()){
		node now=q.top();q.pop();
		if(disn[now.x]<now.dis) continue;
		for(auto s:e[now.x]){
			node nxt=node{s.to,now.dis+s.w};
			if(disn[nxt.x]>nxt.dis){
				pren[nxt.x]=now.x;
				disn[nxt.x]=nxt.dis;
				q.push(nxt);
			}
		}
	}
	rep(i,1,n){
		if(pre1[i]) suf1[pre1[i]].pb(i);
		if(pren[i]) sufn[pren[i]].pb(i);
	}
	queue<int> qL,qR;
	vector<int> P;
	for(int p=n;p!=1;p=pre1[p]){
		P.pb(p),qL.push(p),qR.push(p),L[p]=p,R[p]=p;
		for(auto s:e[pre1[p]])
			if(s.to==p&&s.w==dis1[p]-dis1[pre1[p]]) onp[s.id]=1;
	}
	P.pb(1);qL.push(1);qR.push(1);L[1]=1;R[1]=1;
	reverse(all(P));
	while(!qL.empty()){
		int x=qL.front();qL.pop();
		for(int s:suf1[x]){
			if(L[s]) continue;
			L[s]=L[x];
			qL.push(s);
		}
	}
	while(!qR.empty()){
		int x=qR.front();qR.pop();
		for(int s:sufn[x]){
			if(R[s]) continue;
			R[s]=R[x];
			qR.push(s);
		}
	}
	rep(i,1,siz(P)) num[P[i-1]]=i;
	build(1,1,siz(P));
	rep(i,1,m){
		if(onp[i]) continue;
		int len=min(dis1[u[i]]+w[i]+disn[v[i]],disn[u[i]]+w[i]+dis1[v[i]]);
		upd(1,num[L[u[i]]],num[pre1[R[v[i]]]],len);
		upd(1,num[L[v[i]]],num[pre1[R[u[i]]]],len);
	}
	while(Q--){
		int t,x;
		cin>>t>>x;
		if(!onp[t]){
			if(x>=w[t]) cout<<dis1[n]<<'\n';
			else{
				cout<<min(dis1[n],min(dis1[u[t]]+x+disn[v[t]],dis1[v[t]]+x+disn[u[t]]))<<'\n';
			}
		}else{
			if(x<=w[t]) cout<<dis1[n]-w[t]+x<<'\n';
			else{
				int PR;
				if(pre1[u[t]]==v[t]) PR=v[t];
				else PR=u[t];
				cout<<min(dis1[n]-w[t]+x,ask(1,num[PR]))<<'\n';
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	int T;for(cin>>T;T--;)
		solve();
	return 0;
}

标签:Taxi,dis1,Fee,int,CF1163F,短路,tr,MAXN,dis
From: https://www.cnblogs.com/ZCETHAN/p/16811244.html

相关文章