AtCoder Regular Contest 011 C - ダブレット

問題

　小文字からなる英単語を変換していく遊びを考える。可能な変換は単語内の1文字を別の文字へと変える操作のみであり、最初の単語と最後の単語、そして経由可能な単語のリストを与えるので最小の変換回数での変換とその過程を示せ。

解法

　リストの重複を削除し、最初と最後の単語を挿入して、最初の単語を始点とした経路復元付きダイクストラ法を行う。

反省

　19分27秒でAC。10分で考察して10分で実装という感じ。そこまで突っかかる要素もなかったわりには時間がかかっている気がする。

　それにしても昔のARCはちょっと簡単めですね。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string first, last;
    ll N;
    cin >> first >> last >> N;
    if (first == last) {
        cout << 0 << endl;
        cout << first << endl;
        cout << last << endl;
        return 0;
    }

    vector<string> s(N);
    for (ll i = 0; i < N; i++) {
        cin >> s[i];
    }

    //重複とfirst, lastを除去
    sort(s.begin(), s.end());
    unique(s.begin(), s.end());
    for (auto itr = s.begin(); itr != s.end(); itr++) {
        if (*itr == first || *itr == last) {
            itr = s.erase(itr);
        }
    }

    //先頭にfirstとlastを挿入
    s.insert(s.begin(), { first, last });

    //Nが変化している可能性があるので取り直す
    N = s.size();

    //隣接リストを構築
    vector<vector<ll>> connect(N);
    for (ll i = 0; i < N; i++) {
        for (ll j = i + 1; j < N; j++) {
            //ハミング距離が1であるか判定
            ll num = 0;
            for (ll k = 0; k < (ll)s[i].size(); k++) {
                if (s[i][k] != s[j][k]) {
                    num++;
                }
            }
            if (num == 1) {
                connect[i].push_back(j);
                connect[j].push_back(i);
            }
        }
    }

    //経路復元付きダイクストラ法
    vector<ll> cost(N, INT_MAX), pre(N, -1);
    struct Element {
        ll cost;
        ll curr;
        //priority_queueでコストの小さいものから出すために
        //普通とは逆の向きで不等号を定義する
        bool operator<(const Element& rhs) const {
            return cost > rhs.cost;
        }
    };

    priority_queue<Element> pq;
    cost[0] = 0;
    pq.push({ 0, 0 });
    while (!pq.empty()) {
        auto t = pq.top();
        pq.pop();

        ll new_cost = t.cost + 1;
        for (ll next : connect[t.curr]) {
            if (new_cost < cost[next]) {
                cost[next] = new_cost;
                pre[next] = t.curr;
                pq.push({ new_cost, next });
            }
        }
    }

    //cost[1]がlastへのコスト
    if (cost[1] == INT_MAX) {
        cout << -1 << endl;
    } else {
        //過程の単語数はその-1
        cout << cost[1] - 1 << endl;
        vector<string> ans;
        for (ll i = 1; pre[i] != -1; i = pre[i]) {
            ans.push_back(s[i]);
        }
        ans.push_back(first);
        reverse(ans.begin(), ans.end());
        for (auto str : ans) {
            cout << str << endl;
        }
    }
}