競プロ初中級者100問

ABC012D バスと避けられない運命

この記事で使うアルゴリズム

ワーシャルフロイド法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc012/tasks/abc012_4

この問題はワーシャルフロイド法を用いて解くことができます。

解説

この問題は自宅から会社まで出来るだけ時間がかからないようにしたいので、時間をコストとした最短経路問題と言えます。

さらに、自宅と会社の位置は決まっていないため全てのバス停間の最短経路を求める必要があります。このような問題は最短経路問題の中でも全点対最短経路問題と言います。

解法としては

  • ダイクストラ法をN回適用する
  • ワーシャルフロイド法
    などが考えられます。どちらも計算量はO(N^3)です。

今回は実装が簡単である解法、ワーシャルフロイド法で解きたいと思います。Python3だとTLEとなってしまうので、PyPy3を利用します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N, M = map(int, input().split())
INF = 10**10
cost = [[INF]*N for _ in range(N)]
for n in range(N):
    cost[n][n] = 0
for m in range(M):
    a, b, t = map(int, input().split())
    cost[a-1][b-1] = t
    cost[b-1][a-1] = t

for i in range(N): # 中継点
    for j in range(N): # 始点
        for k in range(N): # 終点
            cost[j][k] = min(cost[j][i]+cost[i][k], cost[j][k])

ans = INF
for n in range(N):
    mx = max(cost[n])
    if mx < ans:
        ans = mx
print (ans)

記事情報

  • 投稿日：2020年4月20日
  • 最終更新日：2020年5月8日