巡回セールスマン問題のまとめ
①鉄則本B23TravelingSalesman Problem すべての都市を巡るので、最初は都市1からスタートするとしても一般性を失わない
dp[i][j]=これまでに訪れた都市がi,今いる都市がjとしたときの移動距離の最小値というDPを考える。
iのk番目のbitが立っているとき、都市kにすでに訪れていることを示す。
まずdp[0][0]=0とする。このときdp[1][0]=0ではない。最終的にスタート地点に戻ってこなければならないので、都市1にはまだ訪れていないことにしておく。
遷移は、まだ都市kを訪れていないようなdp[i][j]から都市kに移動することを考える。都市jからkへ移動することになるので、chmin(dp[i+(1<<k)][j],dp[i][j]+都市jからkの距離)になる。
都市jとkの距離は、jとkのx座標の差の二乗+jとkのy座標の差の二乗で求められる。(三平方の定理)
最初に都市1からスタートしたとき、最後にいるのは都市1なので、dp[(1<<n)-1][0]が答え。
(今回はN<=15なので気にする必要はないが、シフト演算子を使うときにNが32を超える場合はオーバーフローに注意)
②ABC180E Traveling Salesman among Aerial Cities ①の解答を三次元に対応するように書き換えるだけ。
今回は「最初は都市1からスタートする」が問題文中に明記されている。(わかりやすさのため？)
①では答えが小数になっていたが、今回は小数点以下を出力するとWAになるので注意。
スタート地点とゴール地点とお菓子の場所を頂点とする巡回セールスマン問題ととらえることができる。
答えはdp[i][ゴール地点]がt以下であるiのうち、立っているbitの数が一番多いiの立っているbitの数。
あらかじめ点同士の距離をBFSなどで計算しておく。
まずそれぞれの頂点に番号を振る。0→S、1→G、2以上は順番に番号を振っていく。
mapで座標と番号を対応付けておく。
次にそれぞれの頂点からBFSを行い、dist[i][j]を頂点iから頂点jまでの距離として更新する。
それぞれの頂点の間の距離を計算出来たら、あとは巡回セールスマン問題を解くだけ！！
頂点数は最大で18個のoとスタート地点、ゴール地点を合わせた20個となる。オーバーフローは気にしなくていい。