新しく作ったグラフ上でBFS.
もとのグラフを \(G = (V,E),\ V = N\) とする． 二人いるので，それらの居る場所をペアで管理してBFS. そのために，拡張したグラフ \(\hat{G} = ( \hat{V}, \hat{E}) \) を作る． \(\hat{V} = V \times V\)．
二人が(\(cx,cy\)) に居るとするとき， (\(nx, ny\)) に移動したい． ルールにより， \(nx \in to_{cx}\) かつ \(ny \in to_{cy}\) かつ \(c_{nx} \neq c_{ny}\) が移動できる必要十分条件．
計算量
\(G\) において辺の本数が少ない ということから， \(\hat{G}\) においてBFSするときに辿る辺が少ない． そのため，BFSが間に合う． 実際， \begin{align} (\sum_{cx \in N} \vert to_{cx} \vert ) (\sum_{cy \in N} \vert to_{cy} \vert ) \leq (2M)^2 \end{align} 程度で抑えらえる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll t; cin >> t;
rep(_,t){
ll n,m; cin >> n >> m;
vll c(n); cinv(c);
vvll to(n);
rep(i,m){
ll a, b; cin >> a >> b;
--a, --b;
to[a].push_back(b);
to[b].push_back(a);
}
auto bfs = [&](ll sx, ll sy) -> void {
queue<pll> que;
auto push = [&](ll x, ll y, ll d) -> void {
if(vis[x][y]) return;
vis[x][y] = true;
que.push({x,y});
dis[x][y] = d;
};
push(sx, sy, 0);
while(que.size()){
auto [cx, cy] = que.front(); que.pop();
ll d = dis[cx][cy];
for(auto ny: to[cy]){
for(auto nx: to[cx]){
if(c[nx] != c[ny]){
push(nx, ny, d+1);
}
}
}
}
if(dis[n-1][0] < INFL){
cout << dis[n-1][0] << endl;
}else{
cout << -1 << endl;
}
};
bfs(0,n-1);
}
return 0;
}
