【AtCoder版！蟻本】ABC012 D - バスと避けられない運命【Warshall-Floyd】

AtCoder版！蟻本のWarshall-Floydの例題としてあげられているABC012 D - バスと避けられない運命をPythonで解いていきます。

リンク

D - バスと避けられない運命

ABC012 D - バスと避けられない運命

問題文

高橋君は、バスがあまり好きではありません。ですが、社会に出ると、バスを乗るという行為を避けることはできません。

社会人になると、自宅から会社まで、バスで通わなければなりません。高橋君はまだ内定を貰っていないので、会社の場所は解りません。

高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。 この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。

追記：なお、最悪のケースとは、バスに乗る時間の合計が最も短くなるように、乗るバスを選択した時に、最もバスに乗る時間の合計が長くなってしまうような位置に会社があるケースのことを指します。また、自宅から会社に行く際に、高橋君が乗るバスを選ぶことができ、高橋君はバスに乗る時間の合計が最も短い経路を選択するものとします。

各バスは、2 つのバス停を往復するように走っており、行き・帰りでかかる時間に差はありません。 バスにはいつでも乗ることが可能であり、乗継にかかる時間などは無視することが可能です。

また、自宅や会社はバス停に隣接しており、他のバス停まで歩いたり、バス以外の手段で移動することはできません。

高橋君が引っ越すべき場所を求め、そこに引っ越した際の、バスに乗らなければならない時間の最大値を出力してください。

制約

・1 行目には、バス停の数を表す整数 N(2≦N≦300) と、路線の数を表す整数 M(N−1≦M≦44850) が、スペース区切りで与えられる。
・続く 2 行目から M 行は、バスの情報を表す。 i 番目の行には、バスの出発地点と往復する 2 つのバス停を表す番号 ai, bi(1≦ai,bi≦N) と、その移動に何分かかるかを表す数字 ti(1≦ti≦1000) が、それぞれ整数で与えられる。
・辿り着けないバス停のペアは存在しないことが保証されている。
・ai≠bi であることが保障されている。
・ある 2 つのバス停を往復する路線は、高々 1 つしか存在しない。

解答例

def warshall_floyd(d):
    for k in range(n): # 中継点
        for i in range(n): # 始点
            for j in range(n): # 終点
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


n, m = map(int,input().split())

d = [[float("inf") for _ in range(n)] for _ in range(n)]

for i in range(n):
    d[i][i] = 0

for i in range(m):
    a, b, t = map(int,input().split())
    d[a-1][b-1] = t
    d[b-1][a-1] = t

warshall_floyd(d)

ans = float("inf")

for i in range(n):
    ans = min(ans, max(d[i]))

print(ans)

解説

N個のバス停から任意の点をゴール地点とするとき、各頂点との距離の最大値が最小となるスタート地点を選び、スタート地点からゴール地点の距離の最大値を答える問題です。

任意の2点間の最小距離をワーシャル・フロイド法を使用します。

各頂点間の最短距離を配列d（初期条件はinf）としました。

同じ頂点間の移動は0なのでd[i][i] = 0とします。

最短距離はワーシャル・フロイド法で求めました。
ワーシャル・フロイドは中継点kと始点i、および終点jの3重ループを回します。
iからjへの移動において、各頂点kを経由した場合の最小値を更新していきました。

ワーシャル・フロイドによりdに各頂点間の最小距離が格納されます。

最後に各頂点を始点としたとき距離の最大値を調べ、最小となる値を出力すればOKでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク