山区医疗点选址与道路维修优化问题

假设某山区中有100个村庄，现在要在村庄中建立几个医疗点，方便村民看病。图1中给出这100个村庄的位置及可选道路连接示意图。附件数据的'位置'表单给出了这100个村庄的坐标（单位：米），附件数据的'连接道路'表单给出了可供选择的道路。现在要在100个村庄中建立3个医疗点，并在可选道路中根据需要进行部分道路维修，假定村民看病都选择维修后的道路。

问题1. 如果各村庄村民到医疗点的距离太远，不便于看病，因此站在村民角度出发，希望各村庄村民到医疗点的距离尽量小。如果要使各村庄村民到医疗点的距离总和S1最小，请问这3个医疗点分别建立在何处最好？总距离S1是多少？各村庄村民都选择最近的医疗点看病，请问应该维修哪些道路，维修道路总里程S2是多少？作图用不同颜色标记各村庄到对应医疗点使用的道路。

问题2. 由于每条道路维修都需要成本，因此站在道路维修公司角度出发，希望维修的成本尽量低。假定问题1中得到的医疗点不变，应该维修哪些道路，使得维修成本最低。给出维修道路的总长度S2，并作出图形。同时根据维修的道路，计算各村庄到医疗点的总距离S1。

问题3. 实际中，我们既希望村民到医疗点很方便，同时希望维修的道路成本尽量小。因此既希望村庄村民到医疗点的总距离S1尽量小，又希望维修的道路总里程S2尽量小，但二者通常无法同时达到最小。如果让这两种距离和S1+S2最小，应如何设置医疗点。给出总距离，并作出维修道路的图形。比较问题1和问题2，S1+S2减少多少。

题目分析内容：

**问题1：**这是一个经典的设施选址问题，可以使用贪心算法来解决。首先，选取一个医疗点，计算所有村庄到该点的距离，并标记距离最近的三个村庄为该点的服务范围。接下来，选取一个未被服务的村庄，计算它到三个医疗点的距离，并将其标记为距离最近的一个医疗点的服务范围内。重复以上步骤，直到三个医疗点都被选出。最终，计算所有村庄到医疗点的距离总和S1，并记录每个村庄所选的医疗点。

**问题2：**根据问题1的结果，可以计算出每个村庄到所选医疗点的路径。接着，对可选道路进行修复，使得所选医疗点之间的路径最短。具体地，可以使用Dijkstra算法来计算两两医疗点之间的最短路径，并对路径上的道路进行修复。最终，计算修复的道路总长度S2，并记录每个村庄到所选医疗点的路径。

**问题3：**可以将问题1和问题2的结果综合起来，构建一个带权图。其中，每个村庄和每个医疗点分别为图中的节点，它们之间的距离为节点之间的边权。接着，可以使用最小生成树算法来求解S1+S2最小的医疗点选址和道路修复方案。最终，计算S1+S2的值，并记录每个村庄到所选医疗点的路径和修复的道路。