简述题意:
现有 nnn 个村庄,村庄之间存在一些土路,它们共同构成一张无向联通图。
我们需要从中选出 mmm 个村庄修建医院,为了方便就医,还需要将一些土路改造为公路。因此我们需要考虑修路成本和方便程度两个因素。
定义方便程度为:每个村庄到距离最近的有医院的村庄的距离之和。
定义修路成本为:将每个村庄到距离最近的有医院的村庄所经过的土路组成一个集合,修路成本为这些土路的长度之和。
需要设计一个方案,使得修路成本和方便程度的和最小。