この記事で使うアルゴリズム
ワーシャルフロイド法
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/abc074/tasks/arc083_b
この問題を解く前に、ワーシャルフロイド法を用いた最短経路問題の解き方について理解しておくことをお勧めします。
解説
2つの問題を同時に解いていきます
- 都市
u
から都市v
への最短経路の長さとなるような道路の構造が存在するか - 存在する道路の長さの和が最小となるようなものについて、その和
都市u
から都市v
への最短経路の長さとなるような道路の構造が存在するか
都市u
から都市v
へ移動する間にどの別の1つの都市を通っても、表に記された値より小さいコストで移動できないことを確認すれば良いです。
存在する道路の長さの和が最小となるようなものについて、その和
2つ目の問題は、都市u
から都市v
へ移動する間にどの別の1つの都市を通っても、表に記された値と等しいコストで移動できない場合、直接結ぶ道路が必要ということになります。そのようなコストを足し合わせていけば良いです。
ポイント
u < v
とする- 道路は双方向に結ばれているので、二重にカウントしてはならない
u != v
とした方が、条件分岐の実装が楽になる
cost[u][u] = INF
とするcost[u][u]=0
としてしまうと、u->u->v
とu->v
の値が常に等しくなる。これを避けた方が条件分岐の実装が楽になる
コード
1 | N = int(input()) |
記事情報
- 投稿日:2020年4月22日
- 最終更新日:2020年5月8日