题解 | #Freckles#

import math

# 最小生成树 prim
# 边选择方式：普里姆算法也是一种贪心算法，但是它是基于 节点 的，每次选择与当前已选节点集合相连的且权重最小的边，确保连通性。
# 实现细节：普里姆算法通常使用 优先队列（Priority Queue）来管理节点之间的边，以快速找到下一条最小权重的边。
def distance(point1, point2):
    """计算两点之间的距离"""
    return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)


def prim(points):
    # 点的数量
    n = len(points)
    # 邻接矩阵:（i，j）表示 点i到点j的距离
    adj_matrix = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            dist = distance(points[i], points[j])
            adj_matrix[i][j] = adj_matrix[j][i] = dist

    # 到当前最小生成树的最小距离：默认+∞
    min_weight = [math.inf] * n
    # 标记是否已经加入到最小生成树中
    visited = [False] * n
    # 选择第一个点作为起点
    min_weight[0] = 0
    # 总长度
    total_length = 0

    for _ in range(n):
        u = -1
        # 选择一个未访问的点使得距离最小
        for i in range(n):
            # 如果 该点未被访问 且（访问的是第一个点 或 当前存在更短路径）
            if not visited[i] and (u == -1 or min_weight[i] < min_weight[u]):
                u = i
        visited[u] = True  # 标记为已访问
        total_length += min_weight[u]  # 累加总长度

        # 更新未访问的点到当前最小生成树的距离
        for v in range(n):
            if not visited[v] and adj_matrix[u][v] < min_weight[v]:
                min_weight[v] = adj_matrix[u][v]
    # print(sum(min_weight))
    return total_length


# 输入处理
n = int(input())
points = [tuple(map(float, input().split())) for _ in range(n)]

# 计算最小生成树的总长度并输出
print(f"{prim(points):.2f}")

最小生成树