Mujin Programming Challenge 2018:E - 迷路
問題
https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e
考え方
辺を拡張してダイクストラ法を適応させる拡張ダイクストラ法の問題である。ある時刻 において、文字列 の情報から次に上下左右に進むまでにかかる時間が分かる。まずこの各時刻 における上下左右の移動コストを求めることが必要。
これが求められればあとは普通のダイクストラ法と同じ要領で、時刻 における移動コスト を先に求めておいた表から計算して、解を求めることができる。
Submission #4087944 - Mujin Programming Challenge 2018
どこに着目して考察するべきだったか
移動コストが時刻によって可変になることに気づく必要がある。
何がバグっていたか
得た知見(典型ポイント)
- 辺のコストが拡張される拡張ダイクストラ法