问题描述： n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度．现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短．设计一程序求解此问题． 基本要求： 用邻接矩阵表示无向网，应显示所选中的村庄到各村庄的最短距离。

这个问题是一个经典的最小半径生成树问题，可以用Prim算法或者Kruskal算法来解决。下面是用Prim算法的示例代码：

import sys

def prim(graph):
    n = len(graph)
    # 初始化
    visited = [False] * n
    dist = [sys.maxsize] * n
    parent = [-1] * n
    dist[0] = 0

    for i in range(n):
        # 找到未访问过的最近的节点
        u = -1
        for j in range(n):
            if not visited[j] and (u == -1 or dist[j] < dist[u]):
                u = j

        # 标记为已访问
        visited[u] = True

        # 更新与节点u相邻的节点的距离
        for v in range(n):
            if not visited[v] and graph[u][v] != 0 and graph[u][v] < dist[v]:
                dist[v] = graph[u][v]
                parent[v] = u

    return parent, dist

def main():
    n = int(input("请输入村庄个数："))
    graph = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                w = int(input("请输入村庄{}到村庄{}的距离：".format(i+1, j+1)))
                graph[i][j] = graph[j][i] = w

    parent, dist = prim(graph)

    # 找到半径最小的村庄
    hospital = -1
    radius = sys.maxsize
    for i in range(n):
        max_dist = -1
        for j in range(n):
            if i != j and parent[j] == i:
                max_dist = max(max_dist, dist[j])
        if max_dist < radius:
            radius = max_dist
            hospital = i

    print("新建医院的位置：村庄{}".format(hospital+1))
    print("到其他村庄的最短距离：")
    for i in range(n):
        if i != hospital:
            print("村庄{}：{}".format(i+1, dist[i]))

if __name__ == '__main__':
    main()

示例输入：

请输入村庄个数：5
请输入村庄1到村庄2的距离：2
请输入村庄1到村庄3的距离：5
请输入村庄1到村庄4的距离：3
请输入村庄1到村庄5的距离：7
请输入村庄2到村庄3的距离：4
请输入村庄2到村庄4的距离：5
请输入村庄2到村庄5的距离：6
请输入村庄3到村庄4的距离：1
请输入村庄3到村庄5的距离：2
请输入村庄4到村庄5的距离：3

示例输出：

新建医院的位置：村庄1
到其他村庄的最短距离：
村庄2：2
村庄3：3
村庄4：3
村庄5：5