この記事で使うアルゴリズム
ダイクストラ法
幅優先探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_e
この問題は幅優先探索とダイクストラ法を用いて解くことができます。
注意
この問題をPython
で解こうとした場合、多くの実装ではPython3
で解くとTLE
、PyPy3
で解くとMLE
になってしまいます。それを回避するためには本質的ではない計算量の削減も必要です。他の言語で挑戦するか、どうしてもPython
で挑戦したい方はAC
されている方のコードを参考にしましょう。(かなり苦しみました)
ダイクストラ法の練習のためには、こちらの問題よりも下記の問題に取り組むことをオススメします。
- ほぼ同様の問題です。こちらは
Python3
で問題なく通せます。
- 上の問題よりも簡単です。
GRL1A Single Source Shortest Path
- さらに簡単です。
AOJ(Aizu Online Judge)
というサイトの問題です。ダイクストラ法の基礎を学びたければこちらも良いでしょう。
方針
基本的には、解説の通りに実装すれば良いです。
- 町iから町jまでタクシーを途中で乗り換えることなく行けるかどうかを判定する
- 幅優先探索
- 町iから町jまでタクシーを途中で乗り換えることなく行ける場合,町iから町jにコストCiの辺があると考える
- 単一始点最短経路を求める
- ダイクストラ法
コード
1 | import heapq |
記事情報
- 投稿日:2020年4月25日
- 最終更新日:2020年5月8日