You are given a map of cities with roads connecting some of them, as well as the length of each road. You have to choose cities in which you will build schools, such that the distance from any city to the nearest city with a school is at most 10 miles, and so that the total number of schools is as small as possible. 题目要求用贪心找出一个解，并证明这个解并不是最优的。 第一反应是求 Minimal Spanning Tree，然后在 Tree 上任意取一个 Vertex，建一个学校，然后把这个节点可以覆盖的 Vertices 去掉，重复，直到没有未覆盖的 Vertex。但是想了以下觉得不对，然后又想是不是对每个 Vertex 作为起点做一次 Dijkstra shortest path，然后每做完一次，从起点建学校，逐步覆盖所有的，然后取所有情况下最优的。无论上述哪一种，都觉得有问题。顺便求教最优解应该怎么求。