Mujin Programming Challenge 2018：E - 迷路

問題
解法
解答

問題

beta.atcoder.jp

解法

ダイクストラ法を使う．この中で，あるマスである方向に動けるようになるまでずっとループを回していると O(NMKlogNM) になり間に合わないので，時刻 0 ~ K - 1 のそれぞれの時，次に上下左右に動ける時刻を O(1) で求められるように前計算をしておくことで計算量を O(NMlogNM) まで落とすことが出来る．