#P3479. [Usaco2014 Mar]Watering the Fields
[Usaco2014 Mar]Watering the Fields
Watering the Fields
题目描述
因降雨不足,农夫约翰想在他的 块田之间铺设水管。第 块田位于平面上互不相同的点 。在田 与田 之间铺一条水管的费用为
承包商只肯铺设费用至少为 的水管。约翰希望任意两块田之间都有一条由水管组成的通路,求满足条件的最低总费用。
输入格式
第一行包含两个整数 。
接下来 行,第 行包含两个整数 。
输出格式
输出一个整数,表示最低总费用。如果不能连通所有田,输出 。
样例 #1
3 11
0 2
5 0
4 3
46
和 之间的费用为 ,不能铺管。把这两块田分别与 相连的费用为 和 ,总费用为 。
数据范围
,,。