刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

编程实现：

蚂蚁王国住着 N 只蚂蚁，每只蚂蚁都有自己的领地，领地之间可以直接到达或经过其他领地间接到达，可以直接到达的领地之间的道路距离都为 1，但所有领地都有一条唯一的最短路径可以相互到达。

现要在 N 块领地（依次编号为 1~N）中，选出一块领地建立游乐场，使得所有蚂蚁到游乐场的最小距离总和是 N 种情况中最小的。

例如：N = 8，1~8 号领地之间的连接关系为：1 和 5、2 和 6、3 和 6、4 和 5、5 和 6、4 和 7、5 和 8。

如果将游乐场创建在 5 号领地，最小距离总和为 10。

1 号到 5 号距离为 1；2 号到 5 号距离为 2；3 号到 5 号距离为 2；4 号到 5 号距离为 1；6 号到 5 号距离为 1；

7 号到 5 号距离为 2；8 号到 5 号距离为 1。

如果将游乐场创建在 6 号领地，最小距离总和为 12。

1 号到 6 号距离为 2；2 号到 6 号距离为 1；3 号到 6 号距离为 1；4 号到 6 号距离为 2；5 号到 6 号距离为 1；

7 号到 6 号距离为 3；8 号到 6 号距离为 2。

……

可以发现，将游乐场创建在 5 号领地，最小距离总和 10 是最小的，故输出 10。

输入描述：

第一行输入一个正整数 N（2≤N≤20），表示领地数量

接下来输入 N-1 行，每行包含两个正整数（1≤正整数≤N，两个正整数不相同），表示两块领地相互之间可以直接到达，正整数之间以一个英文逗号隔开（数据保证 N 块领地相互之间可以到达）

输出描述：

输出一个整数，表示 N 种情况中最小距离总和的最小值


样例输入：

8
1,5
2,6
3,6
4,5
5,6
4,7
5,8

样例输出：

10

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythonfrom collections import defaultdictdef min_distance_sum(N, edges):# 构建邻接矩阵graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)# 使用 Floyd-Warshall 算法计算任意两点间的最短距离dist = [[float('inf')] * (N + 1) for _ in range(N + 1)]for i in range(1, N + 1):dist[i][i] = 0for k in range(1, N + 1):for i in range(1, N + 1):for j in range(1, N + 1):dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])# 遍历每个点作为游乐场，计算最小距离总和min_sum = float('inf')for i in range(1, N + 1):total_dist = 0for j in range(1, N + 1):total_dist += dist[i][j]min_sum = min(min_sum, total_dist)return min_sumN = int(input())edges = [tuple(map(int, input().split(','))) for _ in range(N - 1)]print(min_distance_sum(N, edges))```

解析：

【喵呜刷题小喵解析】：

首先，我们需要构建邻接矩阵来表示领地之间的连接关系。在这个问题中，我们使用 Python 的 defaultdict 数据结构来创建邻接矩阵。对于输入的每对连接，我们将其添加到邻接矩阵中。

然后，我们使用 Floyd-Warshall 算法来计算任意两点间的最短距离。Floyd-Warshall 算法是一种动态规划算法，可以计算出任意两点间的最短路径。

最后，我们遍历每个点作为游乐场，计算最小距离总和。对于每个点，我们计算从该点到所有其他点的距离之和，并更新最小距离总和。

在 Python 中，我们可以使用 input() 函数来读取输入，并使用 print() 函数来输出结果。在这个问题中，我们读取领地数量和连接关系，然后调用 min_distance_sum() 函数来计算最小距离总和，并将结果输出到控制台。
创作类型：
原创

本文链接：编程实现： 蚂蚁王国住着 N 只蚂蚁，每只蚂蚁都有自己的领地，领地之间可以直接到达或经过其他领地间接

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share