Shortest Good Path [AtCoder Beginner Contest 244 F]

https://atcoder.jp/contests/abc244/tasks/abc244_f

前提知識

• BFS

解説

https://atcoder.jp/contests/abc244/submissions/30322530

今回の問題はbitmaskを状態として利用したbfsで解くことができる。
状態の持ち方としてbitmaskを利用するという方法はbit全列挙やbitDPでも見られる。
bitmaskを利用する方法については説明しないので、少なくともbit全列挙は理解した上で読んでほしい。

何から始めるか

解法を見れば、なるほどと思う人も多いかもしれない。
複雑な問題設定なので、すこし面食らってしまった人もいるかもしれない。

この問題の特徴としてはN≦17である。
Sとして考えられる文字列は全列挙できるので、それぞれに最短の長さを求めて総和をそのまま取ればよさそう。
逆に言えば、Sとして考えられる文字列のそれぞれについて最短距離を求める必要がある。
なので、以下を定義して考察を始めてみよう。

opt[S] := 文字列Sに関する良いパスのうち最短のものの長さ

最短？

パスが伸びていく過程を考えていくと、パスの長さというのは1つずつしか増えない。
+1ずつであり最短距離と言えばbfsである。
bfsで最短距離を計算していく上で、opt[S] -> opt[next_S]を計算したいという前提に立ってみると、
パスの終端は状態に必要になってくる。
よって、保持する状態を変更しておこう。

opt[S][lst] := 文字列Sに関する良いパス、かつ、最後がlstのパスのうち最短のものの長さ

これでopt[S][lst]からの遷移はopt[next_S][to]と遷移が行えるようになった。
これでbfsをしていけば求めたい最短長が求められる。

msk=0の時がちょっと厄介なので、最初の遷移は別途やってしまうことにして、後はbfsをするだけ。
計算量は分かりにくいがO(2^N(N+M))のはず。

int N, M;
vector<int> E[17];
int opt[1 << 17][17];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    queue<pair<int, int>> que;
    rep(i, 0, N) {
        opt[1 << i][i] = 1;
        que.push({ 1 << i, i });
    }

    while (!que.empty()) {
        int msk, lst;
        tie(msk, lst) = que.front();
        que.pop();

        fore(to, E[lst]) {
            int msk2 = msk ^ (1 << to);
            if (opt[msk2][to] == 0) {
                opt[msk2][to] = opt[msk][lst] + 1;
                que.push({ msk2, to });
            }
        }
    }

    int ans = 0;
    rep(msk, 1, 1 << N) {
        int mi = inf;
        rep(lst, 0, N) chmin(mi, opt[msk][lst]);
        ans += mi;
    }
    cout << ans << endl;
}