kmjp's blog

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

Codeforces #1133 : Div.1 D. Meta Graph

ほどほどの時間で思いつけて良かったね。
https://codeforces.com/contest/2279/problem/D

問題

N点M辺の連結無向グラフGが与えられる。

ここから、以下のグラフf(G)を考える。

  • N^2個の点があり、Uvの書式で表される(1≦U,v≦N)
  • Gにおいてa-b間に辺がある場合、f(G)においてCa-Cb間とAb-Ba間に辺が追加される。

Gが与えられる。
またf(G)上の2点 Wx, Yzが与えられる。Wx-Yzの最短距離を求めよ。

解法

f(G)にはN^2個点があるが、考えるべき点は以下の点と辺で良い。

  • Wv (vは任意)
  • Xv
  • a-b間に辺があるとき、AbとBa

これらの点と辺はO(N+M)個しかないので、普通にBFSすれば間に合う。

int T,N,M;
vector<int> E[202020];
vector<int> E2[1002020];
int W,X,Y,Z;

map<pair<int,int>,int> Vs;
int C;
ll dp[1008080];

void add(int a,int b) {
	if(Vs.count({a,b})==0) {
		Vs[{a,b}]=C++;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		FOR(i,N) E[i].clear();
		cin>>N>>M>>W>>X>>Y>>Z;
		X--,W--,Y--,Z--;
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		C=0;
		Vs.clear();
		
		FOR(i,N) {
			add(W,i);
			add(Y,i);
		}
		x=2*N;
		FOR(i,N) {
			add(i,i);
			FORR(e,E[i]) add(i,e);
		}
		FOR(i,C) {
			E2[i].clear();
			dp[i]=1<<30;
		}
		FOR(i,N) FORR(e,E[i]) if(e<i) {
			E2[Vs[{W,i}]].push_back(Vs[{W,e}]);
			E2[Vs[{W,e}]].push_back(Vs[{W,i}]);
			E2[Vs[{Y,i}]].push_back(Vs[{Y,e}]);
			E2[Vs[{Y,e}]].push_back(Vs[{Y,i}]);
			E2[Vs[{i,i}]].push_back(Vs[{i,e}]);
			E2[Vs[{i,e}]].push_back(Vs[{i,i}]);
			E2[Vs[{e,i}]].push_back(Vs[{e,e}]);
			E2[Vs[{e,e}]].push_back(Vs[{e,i}]);
			
			E2[Vs[{i,e}]].push_back(Vs[{e,i}]);
			E2[Vs[{e,i}]].push_back(Vs[{i,e}]);
		}
		dp[Vs[{W,X}]]=0;
		queue<int> Q;
		Q.push(Vs[{W,X}]);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop();
			FORR(e,E2[cur]) if(chmin(dp[e],dp[cur]+1)) Q.push(e);
		}
		cout<<dp[Vs[{Y,Z}]]<<endl;
		FOR(i,C) {
			E2[i].clear();
		}
	}
}

まとめ

Div1 Dの割には易しい?