Mujin Programming Challenge 2018:E - 迷路

問題

https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e

考え方

辺を拡張してダイクストラ法を適応させる拡張ダイクストラ法の問題である。ある時刻 t において、文字列 d の情報から次に上下左右に進むまでにかかる時間が分かる。まずこの各時刻 t_i における上下左右の移動コストを求めることが必要。

これが求められればあとは普通のダイクストラ法と同じ要領で、時刻 t_i における移動コスト c を先に求めておいた表から計算して、解を求めることができる。

Submission #4087944 - Mujin Programming Challenge 2018

どこに着目して考察するべきだったか

移動コストが時刻によって可変になることに気づく必要がある。

何がバグっていたか

得た知見(典型ポイント)

類題