脳log[20220214]

2022年02月14日 (月) [AtCoder] 精進。第九回 アルゴリズム実技検定 過去問／I 問題 直通エレベータ。考えてもわからなくて飛ばしていた問題。解き直すきっかけはこの前の ABC に関するこれ「時間はかかったけど昨日は直線の上にグラフが見えた」なんだけど、実はこちらの問題は ABC の方より見た目がグラフっぽくてダイクストラ法を使うことは見えていた。見えていなかったのは、エレベーターを使う場合と使わない場合の隣接ノードのみをキューに追加すればいい、ということ。遷移先の候補が多すぎて困っていたのだけど、実はエレベーターを使った移動先と、上下にある一番近くのエレベーター乗降階のみを考えるだけで良かった。提出 #29245963 (AC / 1134 Byte / 703 ms)。