kmjp's blog

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

Codeforces #681 Div1 C. Graph Transpositions

今年も頑張ります。
https://codeforces.com/contest/1442/problem/C

問題

N点M有効辺のグラフが与えられる。
今頂点1にあるトークンを、以下の手順で頂点Nに移動させたい。

  • 辺に沿ってトークンを動かす。これには時間が1かかる。
  • 全有向辺の向きを逆にする。この作業を行うのがK回目とすると、2^(K-1)の時間がかかる。

かかる最短時間を求めよ。

解法

後者の向きの反転処理をO(logN)回行うまでは、現在位置と反転処理回数を状態にもってダイクストラ法を行えばよい。
反転処理をO(logN)回以上行う場合、反転回数が時間の支配的な要素となる。
そこで、BFSの要領で、少ない反転回数で頂点Nに到達する時間を求めて行く。

int N,M;
const ll mo=998244353;
vector<int> E[202020][2];

ll D[22][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x][0].push_back(y);
		E[y][1].push_back(x);
	}
	FOR(i,N) FOR(j,21) D[j][i]=1LL<<60;
	priority_queue<pair<ll,int>> Q;
	D[0][0]=0;
	Q.push({0,0});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second%N;
		int num=Q.top().second/N;
		Q.pop();
		if(D[num][cur]!=co) continue;
		if(num<20) {
			if(co+(1<<num)<D[num+1][cur]) {
				D[num+1][cur]=co+(1<<num);
				Q.push({-D[num+1][cur],(num+1)*N+cur});
			}
		}
		FORR(e,E[cur][num%2]) if(co+1<D[num][e]) {
			D[num][e]=co+1;
			Q.push({-D[num][e],num*N+e});
		}
	}
	ll ret=1LL<<60;
	FOR(i,21) ret=min(ret,D[i][N-1]);
	if(ret==1LL<<60) {
		ll add=1<<19;
		int turn=0;
		set<int> cand;
		FOR(i,N) if(D[20][i]!=1LL<<60) cand.insert(i);
		ll sum=0;
		while(D[20][N-1]==1LL<<60) {
			turn^=1;
			add=add*2%mo;
			sum=(sum+add)%mo;
			FORR(c,cand) Q.push({-D[20][c],c});
			cand.clear();
			while(Q.size()) {
				ll co=-Q.top().first;
				int cur=Q.top().second;
				Q.pop();
				if(D[20][cur]!=co) continue;
				FORR(e,E[cur][turn]) if(co+1<D[20][e]) {
					D[20][e]=co+1;
					Q.push({-D[20][e],e});
					cand.insert(e);
				}
			}
		}
		ret=(sum+D[20][N-1])%mo;
	}
	cout<<ret<<endl;
	
}

まとめ

これ解いたの2020年なんだが…。