この記事で使うアルゴリズム
ワーシャルフロイド法
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja
この問題はワーシャルフロイド法を用いて解くことができます。
解説
このような問題は最短経路問題
の中でも全点対最短経路問題
と言います。
解法としては
- ダイクストラ法をN回適用する
- ワーシャルフロイド法
などが考えられます。
ただし、負の重みがある場合はダイクストラ法を適用することはできません。そのため、今回はワーシャルフロイド法
を用います。負の閉路がある場合、ワーシャルフロイド法
の計算の結果、自身への最短距離dist[n][n]
が負の値となります。
コード
1 | N, M = map(int, input().split()) |
記事情報
- 投稿日:2020年5月31日
- 最終更新日:2020年5月31日