No.34

幅優先探索と DP を組み合わせる.

ある地点 $p$ までたどり着くまでの最小の体力を $V(p)$ とする.

幅優先探索で探索元を $p$, 探索先を $q$ とすると, $V(p)+L(q) \lt V(q)$ のときに探索先は有効となる.