この記事で使うアルゴリズム
ワーシャルフロイド法
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/abc012/tasks/abc012_4
この問題はワーシャルフロイド法を用いて解くことができます。
解説
この問題は自宅から会社まで出来るだけ時間がかからないようにしたいので、時間をコストとした最短経路問題
と言えます。
さらに、自宅と会社の位置は決まっていないため全てのバス停間の最短経路を求める必要があります。このような問題は最短経路問題
の中でも全点対最短経路問題
と言います。
解法としては
- ダイクストラ法をN回適用する
- ワーシャルフロイド法
などが考えられます。どちらも計算量はO(N^3)
です。
今回は実装が簡単である解法、ワーシャルフロイド法
で解きたいと思います。Python3
だとTLE
となってしまうので、PyPy3
を利用します。
コード
1 | N, M = map(int, input().split()) |
記事情報
- 投稿日:2020年4月20日
- 最終更新日:2020年5月8日