No.95

$i$ 番目のノードを訪問すると $1 \dots i-1$ 番目のノードをすべて訪問した場合よりも高い点数を獲得できるので, できるだけ大きい番号のノードを通るようにする.

番号の大きい順に $i$ 番目のノードを新たに訪問ノード集合に加えた場合でも $K$ 歩以内に辿れるかどうかを調べ, 辿れるならば訪問ノード集合に加えるというのを繰り返す.

訪問ノード集合が ${ a_k }$ のときに $K$ 歩以内に辿れるかどうかは, BitDP を使う.

訪問ノード集合の部分集合 $B$ をすべて訪問し, そのうち $b_i$ 番目のノードを最後に訪れるときの最短歩数を $E(B, b_i)$ とすると,

$$E(B, b_i) = \min(E(B \setminus b_j, b_j) + D(b_i, b_j))$$

となる. ただし, $D(i, j)$ は $i$ 番目のノードと $j$ 番目のノードの距離である. これはワーシャル・フロイド法であらかじめ求めておく.