从 0 到各点的最短距离

七个点的带权图，走不到的记 -1。运行下面这段程序：

def build(edges):
    g = {}
    for a, b, w in edges:
        g.setdefault(a, []).append((b, w))
        g.setdefault(b, []).append((a, w))
    for u in g:
        g[u].sort()
    return g

import heapq

def dijkstra(g, s):
    INF = 10 ** 9
    d = {u: INF for u in g}
    d[s] = 0
    done = set()
    pq = [(0, s)]
    while pq:
        du, u = heapq.heappop(pq)
        if u in done:
            continue
        done.add(u)
        for v, w in g[u]:
            if du + w < d[v]:
                d[v] = du + w
                heapq.heappush(pq, (d[v], v))
    return d

g = build([(0, 1, 2), (0, 2, 1), (1, 3, 3),
      (2, 4, 9), (3, 4, 1), (5, 6, 7)])
d = dijkstra(g, 0)
print("/".join(str(d[u]) if d[u] < 10 ** 9 else "-1" for u in sorted(g)))