kmjp's blog

競技プログラミング参加記です

Codeforces #558 Div2 F. Indecisive Taxi Fee

Codeforces

いやこれは割としんどい…。
https://codeforces.com/contest/1163/problem/F

問題

辺に距離が設定された無向グラフが与えられる。
各クエリについて以下に答えよ。なお、各クエリで変更した辺の長さは次のクエリには影響しない。

  • ある1辺の長さを指定した値に変えたとき、頂点1からNへの最短経路長はいくつか。

解法

まず、各頂点vに対し頂点1番と頂点N番の頂点からの距離D(1,v)とD(v,N)を求めておこう。
各クエリでは、頂点U,V間の距離がXになったとする。

先に簡単なケースを片づけておく。

  • 辺の長さが短くなる場合、その辺を通るケースが、元の最短路より短いかを判定すればよい。すなわちmin(D(1,N), D(1,U)+X+D(V,N), D(1,V)+X+D(X,N))が解。
  • そうでない場合、その辺が、元の最短経路上に無いなら、その辺を通る理由はないので元の最短経路が解。

残るは、もともと最短経路上の辺だったのが長くなってしまい、他の辺を迂回した方がいいかもしれないケースである。
そこで、特定の辺を通らない最短ケースを求めることを考えよう。

頂点1からNへの最短経路上に無い頂点において、1番またはN番から到達する際、最大でどれだけパスのprefixおよびsuffixが1からNへの最短経路と一致しない状態で最短路とできるかを求める。
すると、そのprefixとsuffixの間の辺は通らなくてよい。

これを踏まえて、最短経路上にない辺に関し、先に前処理として以下をSegTreeで管理する。
両端U,Vに対し、1-Uの最短経路と1-Nの最短経路のprefixが頂点p個一致し、V-Nの最短経路と1-Nの最短経路のsuffixが頂点s個一致したとする。
元のパスの頂点数をLとすると、クエリにより長くなる点がp番目～(L-s+1)番の間の辺であれば、今見ている辺を通る最短経路は影響を受けない。
という情報を、区間最小値を取れるSegTreeを用いて覚えておけば、各クエリに対してその辺を通らない最短経路長を高速に求められる。

int N,M,Q;
vector<pair<int,int>> E[202020];
int U[202020],V[202020],W[202020],mainpath[202020];
int inmp[202020];
ll D[202020][2];
int from[202020][2];
int frome[202020][2];
int id[202020][2];

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	SegTree_2(){val.resize(NV*2,1LL<<60);};
	
	V getval(int entry) {
		entry += NV;
		ll ret=val[entry];
		while(entry>1) entry>>=1, ret=min(ret,val[entry]);
		return ret;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) val[k]=min(val[k],v);
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
		}
	}
};
SegTree_2<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,M) {
		cin>>U[i]>>V[i]>>W[i];
		U[i]--;
		V[i]--;
		E[U[i]].push_back({V[i],i});
		E[V[i]].push_back({U[i],i});
	}
	FOR(i,N) D[i][0]=D[i][1]=1LL<<60;
	D[0][0]=D[N-1][1]=0;
	priority_queue<pair<ll,int>> PQ;
	PQ.push({0,0});
	PQ.push({0,N+N-1});
	while(PQ.size()) {
		int cur=PQ.top().second%N;
		int id=PQ.top().second/N;
		ll co=-PQ.top().first;
		PQ.pop();
		if(D[cur][id]!=co) continue;
		FORR(e,E[cur]) {
			if(D[e.first][id]>co+W[e.second]) {
				from[e.first][id]=cur;
				frome[e.first][id]=e.second;
				D[e.first][id]=co+W[e.second];
				PQ.push({-D[e.first][id],id*N+e.first});
			}
		}
	}
	
	MINUS(inmp);
	vector<int> C;
	x=N-1;
	while(x) {
		C.push_back(x);
		mainpath[frome[x][0]]=1;
		x=from[x][0];
	}
	C.push_back(0);
	reverse(ALL(C));
	
	FOR(i,C.size()) {
		id[C[i]][0]=id[C[i]][1]=i;
		inmp[C[i]]=i;
	}
	vector<pair<ll,int>> cand;
	FOR(i,N) {
		if(inmp[i]==-1) id[i][0]=N+1;
		cand.push_back({D[i][0],i});
		cand.push_back({D[i][1],N+i});
	}
	sort(ALL(cand));
	FORR(c,cand) {
		x=c.second%N;
		y=c.second/N;
		FORR(e,E[x]) {
			if(mainpath[e.second]==0 && D[x][y]==D[e.first][y]+W[e.second]) {
				if(y==0) id[x][0]=min(id[x][0],id[e.first][0]);
				if(y==1) id[x][1]=max(id[x][1],id[e.first][1]);
			}
		}
	}
	
	FOR(i,M) if(mainpath[i]==0) {
		if(id[U[i]][0]<id[V[i]][1]) st.update(id[U[i]][0],id[V[i]][1],D[U[i]][0]+D[V[i]][1]+W[i]);
		if(id[V[i]][0]<id[U[i]][1]) st.update(id[V[i]][0],id[U[i]][1],D[V[i]][0]+D[U[i]][1]+W[i]);
	}
	
	while(Q--) {
		cin>>x>>y;
		x--;
		ll ret=D[N-1][0];
		if(y<=W[x]) {
			ret=min(ret,D[U[x]][0]+D[V[x]][1]+y);
			ret=min(ret,D[U[x]][1]+D[V[x]][0]+y);
		}
		else if(mainpath[x]) {
			ret=min(D[N-1][0]+(y-W[x]), st.getval(min(id[U[x]][0],id[V[x]][0])));
		}
		cout<<ret<<endl;
	}
	
	
	
	
}

まとめ

細かい部分で割と苦労した。これをなぜDiv2で出してしまったのか…。