原题来自:AHOI 2008
Y
岛风景美丽宜人,气候温和,物产丰富。Y
岛上有 N
个城市,有 N−1
条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是,小可可通过这些道路可以走遍 Y
岛的所有城市。神奇的是,乘车经过每条道路所需要的费用都是一样的。
小可可,小卡卡和小 YY
经常想聚会,每次聚会,他们都会选择一个城市,使得三个人到达这个城市的总费用最小。
由于他们计划中还会有很多次聚会,每次都选择一个地点是很烦人的事情,所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置,希望你为他们的每一次聚会选择一个合适的地点。