Submission #1679759

---

Source Code Expand

import numpy as np

def dijkstra(s):
    new_G = G.copy()
    cand = [i for i in range(N)]
    cand.remove(s)
    while len(cand) != 0:
        point = min(cand, key=lambda x:new_G[s, x])
        cand.remove(point)
        for i in cand:
            if new_G[s, i] >= new_G[s, point] + new_G[point, i]:
                new_G[s, i] = new_G[s, point] + new_G[point, i]
    return np.max(new_G[s, :])


N, M = map(int, input().split(' '))
G = np.zeros([N, N], np.int32)
G.fill(1000 * 300)
for i in range(M):
    a, b, t = map(int, input().split(' '))
    G[a - 1, b - 1] = t
    G[b - 1, a - 1] = t
for i in range(N):
    G[i, i] = 0
worst_time = []
for p in range(N):
   worst_time.append(dijkstra(p))
print(min(worst_time))

Submission Info

Judge Result