把所有房间接起来最省线，为什么从门口走到每间却不一定最短？

"""Minimum total construction cost and single-source path cost are different."""
import heapq
import itertools
import json


def validate(n, edges):
    edges = tuple(edges)  # Input validation must not consume a one-use iterator.
    if type(n) is not int or not 0 <= n <= 64:
        raise ValueError("vertex count must be an integer from 0 to 64")
    seen = set()
    for u, v, weight in edges:
        if any(type(x) is not int for x in (u, v, weight)):
            raise ValueError("vertices and weights must be integers")
        if not 0 <= u < v < n or weight <= 0:
            raise ValueError("require 0 <= u < v < n and positive weight")
        if (u, v) in seen:
            raise ValueError("parallel edges are outside this model")
        seen.add((u, v))
    return edges


def minimum_forest(n, edges):
    edges = validate(n, edges)
    parent, size = list(range(n)), [1] * n

    def root(vertex):
        while parent[vertex] != vertex:
            parent[vertex] = parent[parent[vertex]]
            vertex = parent[vertex]
        return vertex

    chosen = []
    for u, v, weight in sorted(edges, key=lambda e: (e[2], e[0], e[1])):
        a, b = root(u), root(v)
        if a == b:
            continue  # This edge would close a cycle in the selected forest.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
        chosen.append((u, v, weight))
    return chosen


def shortest_paths(n, edges, source):
    edges = validate(n, edges)
    if type(source) is not int or not 0 <= source < n:
        raise ValueError("unknown source")
    adjacency = [[] for _ in range(n)]
    for u, v, weight in edges:
        adjacency[u].append((v, weight))
        adjacency[v].append((u, weight))
    distance, parent = [None] * n, [None] * n
    distance[source] = 0
    queue = [(0, source)]
    while queue:
        cost, u = heapq.heappop(queue)
        if distance[u] != cost:
            continue
        for v, weight in adjacency[u]:
            candidate = cost + weight
            if distance[v] is None or candidate < distance[v]:
                distance[v] = candidate
                parent[v] = (min(u, v), max(u, v), weight)
                heapq.heappush(queue, (candidate, v))
    return distance, sorted(edge for edge in parent if edge is not None)


def components(n, edges):
    # Independent connectivity oracle uses graph traversal, not union-find.
    adjacency = [set() for _ in range(n)]
    for u, v, _ in edges:
        adjacency[u].add(v)
        adjacency[v].add(u)
    remaining = set(range(n))
    groups = set()
    while remaining:
        todo, reached = [min(remaining)], set()
        while todo:
            u = todo.pop()
            if u not in reached:
                reached.add(u)
                todo.extend(adjacency[u] - reached)
        remaining -= reached
        groups.add(frozenset(reached))
    return groups


def exhaustive_minimum_cost(n, edges):
    if n > 5:
        raise ValueError("exhaustive oracle is limited to at most five vertices")
    target = components(n, edges)
    required = n - len(target)
    valid_costs = [sum(e[2] for e in subset)
                   for subset in itertools.combinations(edges, required)
                   if components(n, subset) == target]
    return min(valid_costs)


def exhaustive_distances(n, edges, source):
    if n > 5:
        raise ValueError("exhaustive oracle is limited to at most five vertices")
    adjacency = [[] for _ in range(n)]
    for u, v, weight in edges:
        adjacency[u].append((v, weight))
        adjacency[v].append((u, weight))
    best = [None] * n

    def visit(u, seen, cost):
        if best[u] is None or cost < best[u]:
            best[u] = cost
        for v, weight in adjacency[u]:
            if v not in seen:
                visit(v, seen | {v}, cost + weight)

    visit(source, {source}, 0)
    return best


def main():
    checks = 0

    def check(condition):
        nonlocal checks
        if not condition:
            raise AssertionError("graph check failed")
        checks += 1

    triangle = [(0, 1, 2), (1, 2, 3), (0, 2, 4)]
    forest = minimum_forest(3, triangle)
    original_distances, shortest_tree = shortest_paths(3, triangle, 0)
    tree_distances, _ = shortest_paths(3, forest, 0)
    check(sum(e[2] for e in forest) == 5)
    check(sum(e[2] for e in shortest_tree) == 6)
    check(original_distances == [0, 2, 4])
    check(tree_distances == [0, 2, 5])
    check(minimum_forest(3, iter(triangle)) == forest)
    check(shortest_paths(3, iter(triangle), 0)[0] == original_distances)
    check(minimum_forest(0, []) == [])
    check(minimum_forest(1, []) == [])
    check(components(4, minimum_forest(4, triangle)) ==
          {frozenset((0, 1, 2)), frozenset((3,))})
    check(shortest_paths(4, triangle, 0)[0] == [0, 2, 4, None])

    pairs = list(itertools.combinations(range(4), 2))
    graph_count = 0
    for weights in itertools.product((0, 1, 2), repeat=len(pairs)):
        # Zero here means absent edge, never a zero-weight edge.
        edges = [(u, v, weight) for (u, v), weight in zip(pairs, weights) if weight]
        graph_count += 1
        selected = minimum_forest(4, edges)
        check(sum(e[2] for e in selected) == exhaustive_minimum_cost(4, edges))
        check(components(4, selected) == components(4, edges))
        check(len(selected) == 4 - len(components(4, edges)))
        for source in range(4):
            distances, _ = shortest_paths(4, edges, source)
            check(distances == exhaustive_distances(4, edges, source))

    invalid = [(2, [(0, 1, -1)]), (2, [(0, 0, 1)]),
               (2, [(0, 1, 1), (0, 1, 2)]), (2, [(0, 2, 1)]),
               (2, [(0, 1, True)]), (True, [])]
    for n, edges in invalid:
        try:
            minimum_forest(n, edges)
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid graph accepted")
    print(json.dumps({"checks_passed": checks, "exhaustive_small_graphs": graph_count,
                      "vertices": {"0": "A", "1": "B", "2": "C"},
                      "available_edges": triangle,
                      "minimum_spanning_tree": {"edges": forest, "total_cost": 5,
                                                "distances_from_A": tree_distances},
                      "shortest_path_tree_from_A": {"edges": shortest_tree, "total_cost": 6,
                                                    "distances_from_A": original_distances},
                      "isolated_D_distances": [0, 2, 4, None],
                      "scope": "positive integer undirected simple graphs; construction cost differs from path cost"},
                     ensure_ascii=False, indent=2))


if __name__ == "__main__":
    main()