Submission #202465

---

Source Code Expand

N,M = map(int,raw_input().split())
l = []
for i in range(M):
    l.append(map(int,raw_input().split()))
    l[i][0]-=1
    l[i][1]-=1



def longest(p):
    nodes = [-1 for i in range(N)]
    isdone = [False for i in range(N)]
    nodes[p] = 0
    c = -1 
    while True:
        a = None
        for i,node in enumerate(nodes):
            if isdone[i] or node < 0:
                continue
            if a == None or node < a:
                a = node
                c = i
        if a==None:
            break
        isdone[c] = True
        for x in l:
            cost = 0
            t = -1
            if x[0]==c:
                t = x[1]
                cost = x[2]
            elif x[1]==c:
                t = x[0]
                cost = x[2]
            else:
                continue
            cost = nodes[c]+cost
            if nodes[t] < 0 or cost < nodes[t]:
                nodes[t] = cost
            
    m = max(nodes)
    return m,nodes.index(m)


c = 10000000
for i in range(N):
    m,p = longest(i)
    c = min(m,c)

print c

Submission Info

Judge Result