ほどほどの時間で思いつけて良かったね。
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の割には易しい?