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

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    graph = [[MAX] * N for _ in range(N)]
    for m in range(M):
        a, b, t = il()
        graph[a - 1][b - 1] = t
        graph[b - 1][a - 1] = t

    graph = csgraph_from_dense(graph)
    graph = floyd_warshall(graph)

    ret = MAX
    for n in range(N):
        ret = min(ret, max(graph[n]))
    print(int(ret))


if __name__ == '__main__':
    main()

考え方

ある頂点から全ての頂点に到達することができる最短経路を求める問題。
回答はワーシャルフロイド法を用いて回答した。

ワーシャルフロイド法の解説
素人によるワーシャルフロイド法 - Qiita

ワーシャルフロイド法を用いることで、
グラフ上の全ての頂点への最短距離を探索することができる。
ただ、自身で実装したワーシャルフロイド法を使用して回答するとLTEとなった。。
Submission #14177612 - AtCoder Beginner Contest 012

そのため、下記を参考に、
scipyのワーシャルフロイド法のモジュールを使用して回答をした。
scipyのFloyd-WarshallとDijkstraのすすめ Python 競技プログラミング Atcoder - じゅっぴーダイアリー

floyd_warshallが出力する2次元配列は、
1次元目が起点となる頂点、2次元目各頂点までの距離となっている。
そのため、各起点となる頂点から他の頂点までの最長距離（最も遠くの頂点）の中で、
最短となる距離を出力することで回答できる。