Submission #202472

---

Source Code Expand

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

N, M = a = ln()
d = [[10000000] * N for i in xrange(N)]
for i in xrange(M):
    a, b, t = ln()
    d[a-1][b-1] = t
    d[b-1][a-1] = t
for i in xrange(N):
    d[i][i] = 0

def dijkstra(s):
    dist = [10000000] * N
    dist[s] = 0
    heap = []
    heapq.heappush(heap, (0, s))
    
    while heap:
        dd, v = heapq.heappop(heap)
        if dist[v] < dd:
            continue
        for i in xrange(N):
            if d[v][i] == 10000000:
                continue
            if dist[i] > dist[v] + d[v][i]:
                dist[i] = dist[v] + d[v][i]
                heapq.heappush(heap, (dist[i], i))
    return dist

result = []
for i in xrange(N):
    result.append(max(dijkstra(i)))
result.sort()
print result[0]

Submission Info

Judge Result