Submission #1245894

---

Source Code Expand

import sys

inf = 1<<30

def solve():
    n, m = map(int, sys.stdin.readline().split())
    cost = [[inf]*n for i in range(n)]

    for u in range(n):
        cost[u][u] = 0

    for i in range(m):
        u, v, l = map(int, sys.stdin.readline().split())
        u, v = u - 1, v - 1
        cost[u][v] = l
        cost[v][u] = l

    dist = [[inf]*n for i in range(n)]

    for u in range(1, n):
        for v in range(1, n):
            dist[u][v] = cost[u][v]
            dist[v][u] = dist[u][v]

    for k in range(1, n):
        for i in range(1, n):
            for j in range(1, n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
                dist[j][i] = dist[i][j]

    ans = inf

    for u in range(1, n):
        for v in range(u + 1, n):
            ans = min(ans, cost[0][u] + dist[u][v] + cost[v][0])

    if ans == inf:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    solve()

Submission Info

Judge Result