[ABC244] F - Shortest Good Path

[Q] https://atcoder.jp/contests/abc244/tasks/abc244_f

N=17と小さいので、bitで状態を管理しそうだと思う。
DP[今いる場所][2^17] = pathの最小値
で管理する。
1. 初期状態は？
2. 遷移は？
3. 解答は？

入力例1
N=3 M=2
1 2
2 3


1. 初期状態
DP[1][001]:1 // 今1にいる。1だけ奇数個ある。pathは1個。
DP[2][010]:1 // 今2にいる。2だけ奇数個ある。pathは1個。
DP[3][100]:1 // 今3にいる。3だけ奇数個ある。pathは1個。

2. 遷移
BFSで、path1->path2を求める。

DP[1][001]->DP[2][011] = 2 // 1->2
DP[2][010]->DP[3][011] = 2 // 2->3
DP[3][100]->DP[2][101] = 2 // 3->2

pathの更新がなくなるまでまわすと、以下の遷移になる。

DP[1][000]:4
DP[2][000]:4
DP[3][000]:4

DP[1][001]:1 // 今1にいて、1だけ奇数個ある状態は、path1
DP[2][001]:3 // 今2にいて、1だけ奇数個ある状態は、path3
DP[3][001]:5 // 今3にいて、1だけ奇数個ある状態は、path5

DP[1][010]:3
DP[2][010]:1
DP[3][010]:3
DP[1][011]:2
DP[2][011]:2
DP[3][011]:6
DP[1][100]:5
DP[2][100]:3
DP[3][100]:1
DP[1][101]:4
DP[2][101]:4
DP[3][101]:4
DP[1][110]:6
DP[2][110]:2
DP[3][110]:2
DP[1][111]:3
DP[2][111]:5
DP[3][111]:3

3. 解答
hashごとに最小pathを加算したいので、

・001の場合
DP[1][001]:1 // 今1にいて、1だけ奇数個ある状態は、path1
DP[2][001]:3 // 今2にいて、1だけ奇数個ある状態は、path3
DP[3][001]:5 // 今3にいて、1だけ奇数個ある状態は、path5

これは DP[1][001]:1 が最小なので、
ans += 1
する。

ans = 14　が解答。

Q. どう遷移させる？
A. BFS。
1から始めた場合、
2から始めた場合、
...
Nから始めた場合、
を同時進行で探索する。

DPを最小値に更新するのだが、1手シミュレートしてみて、もし更新があるならその手を採用する。更新がないなら、同じシチュエーションに短いpathで到達できていることになるので、その探索は捨ててしまっていい。

Q. DFSだとダメ？
A. TLEする。連結で1本道のグラフだった場合、O(N^2)の探索になってしまいそう。

実装

ll DP[18][1 << 17];  // now, hash
ll N, M;
vector<ll> G[20];

int main() {
 cincout();

 cin >> N >> M;
 rep(i, M) {
   ll u, v;
   cin >> u >> v;
   --u, --v;
   G[u].push_back(v);
   G[v].push_back(u);
 }

 // def
 rep(i, (1 << N)) {
   rep(j, N) { DP[j][i] = oo; }
 }

 // BFS
 queue<pll> Q;  // {now, hash}
 rep(i, N) { Q.push({i, (1 << i)}); }
 rep(i, N) { DP[i][1 << i] = 1; }

 ll turn = 0;
 while (!Q.empty()) {
   ll qsz = Q.size();
   ++turn;
   rep(i, qsz) {
     auto &[u, hash] = Q.front();
     for (auto v : G[u]) {
       hash ^= (1 << v); // バックトラック
       if (chmin(DP[v][hash], turn + 1)) {
         Q.push({v, hash});
       }
       hash ^= (1 << v); // 復元
     }
     Q.pop();
   }
 }

 ll ans = 0;

 for (ll i = 1; i < (1 << N); ++i) {
   ll add = oo;
   rep(j, N) { chmin(add, DP[j][i]); }
   // j:今いる場所。i:hash。hashの最小値を取得する。
   ans += add;
 }
 cout << ans << endl;
}

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