边的费用只有0和1，为什么第一次到达一个点还不能定案？

"""A first-discovered route need not be cheapest when some edges cost zero."""
from collections import deque
from itertools import product


def require(ok, message):
    if not ok:
        raise AssertionError(message)


def validate(n, edges, start):
    if type(n) is not int or not 1 <= n <= 12 or type(start) is not int or not 0 <= start < n:
        raise ValueError("1..12 nodes and an existing integer start required")
    if not isinstance(edges, (list, tuple)) or len(edges) > 144:
        raise ValueError("at most 144 directed edges required")
    seen = set()
    for edge in edges:
        if not isinstance(edge, (list, tuple)) or len(edge) != 3:
            raise ValueError("edge must be (from, to, cost)")
        a, b, weight = edge
        if any(type(x) is not int for x in edge) or not (0 <= a < n and 0 <= b < n) or weight not in (0, 1):
            raise ValueError("known integer nodes and cost 0 or 1 required")
        if (a, b) in seen:
            raise ValueError("duplicate directed edge")
        seen.add((a, b))


def distances(n, edges, start=0, first_only=False):
    validate(n, edges, start)
    if type(first_only) is not bool:
        raise ValueError("first_only must be bool")
    graph = [[] for _ in range(n)]
    for a, b, cost in edges:
        graph[a].append((b, cost))
    dist = [None] * n
    dist[start] = 0
    queue = deque([(start, 0)])
    trace = []
    while queue:
        node, recorded = queue.popleft()
        if recorded != dist[node]:
            trace.append(("stale", node, recorded, list(dist)))
            continue
        trace.append(("pop", node, recorded, list(dist)))
        for target, cost in graph[node]:
            proposed = recorded + cost
            better = dist[target] is None or proposed < dist[target]
            if better and (not first_only or dist[target] is None):
                dist[target] = proposed
                entry = (target, proposed)
                if cost == 0 and not first_only:
                    queue.appendleft(entry)
                else:
                    queue.append(entry)
                trace.append(("relax", target, proposed, list(dist)))
    return dist, trace


def simple_path_reference(n, edges, start):
    best = [None] * n
    def walk(node, cost, seen):
        if best[node] is None or cost < best[node]:
            best[node] = cost
        for a, b, weight in edges:
            if a == node and b not in seen:
                walk(b, cost + weight, seen | {b})
    walk(start, 0, {start})
    return best


def main():
    edges = [(0, 1, 1), (0, 2, 0), (2, 1, 0)]
    good, trace = distances(3, edges)
    bad, _ = distances(3, edges, first_only=True)
    print(f"edges={edges}; start=0")
    print(f"first_discovery_only={bad}; zero_one_bfs={good}")
    print(f"stale_queue_records={sum(row[0] == 'stale' for row in trace)}")
    require(good == [0, 0, 0] and bad == [0, 1, 0], "first-discovery counterexample")
    pairs = [(a, b) for a in range(3) for b in range(3) if a != b]
    cases = 0
    for choices in product((-1, 0, 1), repeat=len(pairs)):
        edges = [(a, b, cost) for (a, b), cost in zip(pairs, choices) if cost >= 0]
        for start in range(3):
            actual, _ = distances(3, edges, start)
            require(actual == simple_path_reference(3, edges, start), "all simple paths")
            cases += 1
    require(distances(2, [(0, 0, 0)])[0] == [0, None], "zero self-loop and unreachable node")
    invalid = [(0, [], 0), (3, [(0, 1, 2)], 0), (3, [(0, 1, -1)], 0),
               (3, [(0, 1, True)], 0), (3, [(0, 3, 0)], 0), (3, [], True)]
    for args in invalid:
        try:
            distances(*args)
        except ValueError:
            pass
        else:
            raise AssertionError("invalid input accepted")
    print(f"graphs=729; start_cases={cases}; invalid_inputs=6")
    print("PASS: independent enumeration of simple paths, zero cycles and unreachable nodes")


if __name__ == "__main__":
    main()