[AtCoder] ABC 180 E – Traveling Salesman among Aerial Cities

問題

方針

いわゆる巡回セールスマン問題というやつです。

\( g(i, j)\) を都市 \( i \) から都市 \( j \) に移動するときのコストとします。\( d(i, j) \) を訪れた都市の状態 \( i \) において最終的に都市 \( j \) にいるときのコストとします。都市を訪れた状態 \( i \) は \( N \) ビットで表され、\( k \) ビット目が \( 1 \) であるとき、都市 \( k \) を訪れたことを表します。 初期値は \( d(0, 0) = 0 \) であり、それ以外は、\( d (i, j) = \infty \) とします。更新式は、訪れた都市の状態 \( i \) で最終的に都市 \( j \) にいるときから都市 \( k \) に行くとすると、状態は \( s = j \lor 2^{k – 1} \) となるので、

\[ d(i,s) \leftarrow \min (d(i, s) , d(i, j) + g(i, k))\]

となります。

コード