Submission #202456

---

Source Code Expand

def warshall_froyd(vs, edges, vs_len, es_len):
    inf = float("inf")
    d = [[inf for _ in range(vs_len)] for _ in range(vs_len)]

    for i in range(vs_len):
        d[i][i] = 0
    for i, j, cost in edges:
        d[i][j] = cost

    for k in vs:
        for i in vs:
            for j in vs:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d


def solve(vs, edges, vs_len, es_len):
    d = warshall_froyd(vs, edges, vs_len, es_len)
    s = set()
    for i in range(vs_len):
        s.add(max(d[i]))
    return min(s)


N, M = [int(i) for i in input().split()]
edges = set()
for _ in range(M):
    frm, to, cost = input().split()
    edges.add((int(frm)-1, int(to)-1, int(cost)))
    edges.add((int(to)-1, int(frm)-1, int(cost)))

print(solve(range(N), edges, N, M))

Submission Info

Judge Result