始点に戻らなくていい巡回セールスマン bitDP N=17 (それって最短ハミルトン路) abc190_e

• Quiz
  • E-Magical Ornament
  • https://atcoder.jp/contests/abc190/tasks/abc190_e
• AC
  • https://atcoder.jp/contests/abc190/submissions/19830501
• 解法
  • K<=17と小さいので訪れる順番を全て試すbitDPをしたい
  • 石の数が10⁵と多いが、注目すべき石は17個に抑えられる。17回ダイクストラをして小さいグラフ(頂点数17)を作ってbitDP
• 計算量
  • O(K² 2^K) + 前処理
    • ∵状態数：K 2^K
    • 辺数：それぞれK
• その他
  • editorialによると最短ハミルトン路