E - Swap Places

問題

頂点辺の単純無向グラフが与えられる。頂点1から頂点に、頂点からにそれぞれコマを移動する時の最短ステップ数を答えよ。

atcoder.jp

解法

すんなりと解けた。一回の動作で2つの頂点が移動するという点が厄介かもしれないが、拡張グラフ上でのDijkstraの気持ちになれば見通しが良くなる。
Dijkstra法のキモは、ある状態の最短経路(文脈によっては当然最短経路ではない場合もあるけど)を順次確定させていくことで、効率よく全体の最短経路を求める点である。この問題での状態とは2つのコマの位置、すなわち、である。

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int N,M;
    cin >> N >> M;
    
    vector<int>C(N);
    vector<vector<int>>edge(N);
    
    for(auto& c : C)
        cin >> c;
    for(int i = 0; i < M; ++i)
    {
        int u,v; cin >> u >> v;
        --u; --v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    
    constexpr int inf = 1e9;
    vector<vector<int>>d(N,vector<int>(N,inf));
    d[0][N - 1] = 0;
    
    using p = pair<int, pair<int,int>>;
    priority_queue<p,vector<p>, greater<>>q;
    
    q.emplace(d[0][N-1],make_pair(0,N -1));
    while(not q.empty())
    {
        int cd = q.top().first;
        const auto [u,v] = q.top().second;
        q.pop();
        
        if (cd > d[u][v])
            continue;
        
        for(auto nv : edge[v])
        {
            for(auto nu : edge[u])
            {
                if(nu == nv or C[nv] == C[nu])
                    continue;
                int nxt = cd + 1;
                if(d[nu][nv] > nxt)
                    d[nu][nv] = nxt, q.emplace(d[nu][nv], make_pair(nu,nv));
            }
        }
    }
    cout << (d[N - 1][0] == inf ? -1 : d[N - 1][0]) << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while(T --> 0)
        solve();
}