大概是最小生成树 吧？ 代码未经过验证 如有错误，欢迎指出
# coding=utf8 """ http://data.biancheng.net/view/41.html 克鲁斯卡尔算法(Kruskal算法)求最小生成树 """ from pprint import pprint matrix = [[0.0, 27.31370849898476, 18.899494936611667, 6.0], [27.31370849898476, 0.0, 2.414213562373095, 15.403124237432849], [18.899494936611667, 2.414213562373095, 0.0, 9.0], [6.0, 15.403124237432849, 9.0, 0.0]] MIN = float('inf') SUM = 0 seen = [] # 首先找到整个图中的最小值， 并将该值对应的点作为 起始点（树根） for i in range(len(matrix)): for j in range(i + 1, len(matrix[i])): if matrix[i][j] < MIN: MIN = matrix[i][j] loc = (i, j) seen.append(loc[0]) seen.append(loc[1]) SUM += MIN # 起始根的大小 # print(seen, MIN) # [1, 2] 2.4 def kruskal(matrix): global SUM, seen while len(seen) != len(matrix): # 当未成完整树时进行寻找树的下一个叶子 MIN = float('inf') for i in seen: for j in range(len(matrix[i])): if matrix[i][j] != 0 and matrix[i][j] < MIN and j not in seen: MIN = matrix[i][j] new = j # 记录新元素（叶子） # print(f'i j {(i, j)} MIN {MIN}') seen.append(new) # 添加新元素 SUM += MIN return SUM SUM = kruskal(matrix=matrix) print(format(SUM, '.2f')) # pprint(format(kruskal(matrix=matrix), '.2f')) # 这个保留后成为字符串什么 矩阵不会生成？
# coding=utf8 """ sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2))+(h_1-h_2)*(h_1-h_2)。 【样例输入】 4 1 1 3 9 9 7 8 8 6 4 5 4 【样例输出】 17.41 """ from pprint import pprint N = int(input()) l_l = [] for i in range(N): l_l.append(list(map(int, input().split()))) matrix = [[0 for _ in range(N)] for _ in range(N)] # 生成空矩阵 def distance(l1, l2): # 定义距离公式 dis = ((l1[0] - l2[0])**2 + (l1[1] - l2[1])**2)**(1/2) + (l1[2] - l2[2])**2 return dis # 矩阵填充 for i in range(N): for j in range(N): matrix[i][j] = distance(l_l[i], l_l[j]) pprint(matrix)