五项一起对得上吗

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

运行下面这段程序:

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

def bellman(g, s):
    INF = 10 ** 9
    d = {u: INF for u in g}
    d[s] = 0
    for _ in range(len(g) - 1):
        for u in g:
            if d[u] == INF:
                continue
            for v, w in g[u]:
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
    return d

def make(verts):
    return {u: u for u in verts}

def find(p, x):
    while p[x] != x:
        p[x] = p[p[x]]
        x = p[x]
    return x

def union(p, a, b):
    ra, rb = find(p, a), find(p, b)
    if ra == rb:
        return False
    p[ra] = rb
    return True

def kruskal(edges, verts):
    p = make(verts)
    total = 0
    picked = []
    for a, b, w in sorted(edges, key=lambda e: (e[2], e[0], e[1])):
        if union(p, a, b):
            total += w
            picked.append((a, b))
    return total, picked

import heapq

def prim(edges, verts, s):
    ad = {u: [] for u in verts}
    for a, b, w in edges:
        ad[a].append((w, b))
        ad[b].append((w, a))
    seen = {s}
    pq = [(w, s, v) for w, v in ad[s]]
    heapq.heapify(pq)
    total = 0
    picked = []
    while pq and len(seen) < len(verts):
        w, u, v = heapq.heappop(pq)
        if v in seen:
            continue
        seen.add(v)
        total += w
        picked.append((u, v))
        for w2, x in ad[v]:
            if x not in seen:
                heapq.heappush(pq, (w2, v, x))
    return total, picked

g = build([(0, 1, 2), (0, 2, 1), (1, 3, 3),
      (2, 4, 9), (3, 4, 1), (5, 6, 7)])
ok = (dijkstra(g, 0)[4] == 6
      and dijkstra({0: [(1, 4), (2, 5)], 1: [(3, 1)], 2: [(1, -3)], 3: []}, 0)[3] == 5
      and bellman({0: [(1, 4), (2, 5)], 1: [(3, 1)], 2: [(1, -3)], 3: []}, 0)[3] == 3
      and kruskal([(0, 1, 2), (0, 2, 1), (1, 3, 3), (2, 4, 9), (3, 4, 1)], [0, 1, 2, 3, 4])[0] == 7
      and prim([(0, 1, 2), (0, 2, 1), (1, 3, 3), (2, 4, 9), (3, 4, 1)], [0, 1, 2, 3, 4], 0)[0] == 7)
print(ok)
提交你的答案
请登录后提交答案。
去登录
代码编辑器
Ctrl + Enter 运行
本次输入:
输出:

                        
👩‍🏫
AI
💬 题目评论

全部评论