【ABC】 180 E - Traveling Salesman among Aerial Citie
巡回セールスマン問題(TSP)です。
$N$が17なのでビットDPを使えば計算量的に間に合うようです。
$S$をビット列の集合として以下のDPを作成します。
- DP[S][v]: 訪問済みの集合Sの頂点vからスタートする時の距離の総和
例えば$N=5$の場合、右から順番に都市1, 都市2と対応づけると、$00110$のビット列は都市2と都市3を訪問した状態を表します。
これがDPのSに対応します。
このデータからは都市2→都市3なのか、都市3→都市2の順番で訪問したのかが分かりません。
今までに訪問した都市の順番を保持する必要はなく最後に訪れた都市の番号さえ分かれば良いのでそれをDPのvで保持しています。
都市jからkへ移動する場合、DPの更新は以下の式で行われます。
DP[i|1<<k][k] = min(DP[i|1<<k][k], DP[i][j]+dist[j][k])
ややこしいのがi|1<<kだと思います。
まず1<<kは1を左に$k$だけシフトさせたビット列を作り出します。
例えばS=00110、v=3、k=5の場合を考えます。
1<<k=10000を表します。
これに対して今i=Sなのでi|1<<k=00110 | 10000=10110となります。
これでDP[i|1<<k][k]は都市2,3,5を訪問して都市5にいる状態を表します。
この更新を行い最終的にはDP[n2-1][0]が求める答えになります。
ここでn2 = 1 << nになります。
全体のコードは以下のリポジトリにupしました。 github.com
ちなみにABC180でレーティングが一気に100ぐらい上がりました。
まだ茶色のクソザコですが。
