C - 最後の森 解説 by Kiri8128

公式解説とほぼ同じですが、ヒント 5 に注意すると計算量が改善できます。

ヒント 1 強敵と戦った回数と移動回数を保持する BFS は、始点を固定すると $O(RCK)$ でできます。
ヒント 2 ある地点 $X$ があって、 ① 「村 → $X$ → ほこら → $X$ → 魔王の城」のように動く、 ② $X$ とほこらの往復では、往路と復路で同じ道を通る、 ③ $X$ とほこらの往復「以外」では、同じ強敵がいる場所を複数回通らない、 としてよいです。 つまり、各ステップではそれぞれ（強敵を倒す数を固定したときの）最短路を動くとしてよいです。
ヒント 3 前計算で、村・ほこら・魔王の城からヒント 1 の BFS をしておきます。
ヒント 4 $X$ を固定すると、最善の方法は $O(K^2)$ で計算できます。
ヒント 5 $X$ として、ほこらまたは強敵がいる場所のみ調べれば十分です。
計算量 計算量は、前計算が $O(RCK)$ 、最後の判定が $O(K^3)$ で合計 $O(RCK + K^3)$ です。

投稿日時:
最終更新: