Chương trình tìm chi phí tối thiểu nối tất cả các điểm trong Python

Cho mảng points tọa độ (x,y). Chi phí nối 2 điểm = khoảng cách Manhattan |xi-xj| + |yi-yj|. Tìm chi phí nhỏ nhất để nối tất cả điểm (MST).

Ví dụ: points=[(0,0),(3,3),(2,10),(6,3),(8,0)] → 22.

Giải thuật (Prim + Min Heap)

1. Set points_set = các chỉ số chưa vào MST.
2. Heap [(0, 0)] (chi phí, chỉ số).
3. Set visited_node.
4. Trong khi heap không rỗng và chưa đủ đỉnh:
   • Pop (dist, idx) nhỏ nhất.
   • Nếu idx chưa visited: thêm vào MST, cộng dist, push tất cả cạnh từ idx đến các đỉnh còn lại vào heap.
5. Trả về tổng chi phí.

Ví dụ minh họa

import heapq

def solve(points):
    points_set = set(range(len(points)))
    heap = [(0, 0)]
    visited_node = set()
    total_distance = 0
    while heap and len(visited_node) < len(points):
        distance, current_index = heapq.heappop(heap)
        if current_index not in visited_node:
            visited_node.add(current_index)
            points_set.discard(current_index)
            total_distance += distance
            x0, y0 = points[current_index]
            for next_index in points_set:
                x1, y1 = points[next_index]
                heapq.heappush(heap, (abs(x0 - x1) + abs(y0 - y1), next_index))
    return total_distance

points = [(0,0),(3,3),(2,10),(6,3),(8,0)]
print(solve(points))

Đầu vào

[(0,0),(3,3),(2,10),(6,3),(8,0)]

Đầu ra

22