问题 2624 --[USACO Dec07] 建造路径

2624: [USACO Dec07] 建造路径

时间限制: 1 Sec  内存限制: 128 MB
提交: 31  解决: 10
[提交][状态][命题人:]

题目描述

Farmer John 刚刚得到了几个新农场!他想把这几个农场用路连接起来,这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。

N (1 ≤ N ≤ 1,000) 个农场中,每个农场的位置在坐标平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已经有 M (1 ≤ M ≤ 1,000) 条路以前就被建好了。请你帮助 Farmer John 考虑建设尽量少长度的额外的路,使他的农场连在一起。

输入

 第 1 行: 两个整数: N , M
* 第 2..N+1 行: 两个整数 Xi , Yi
* 第 N+2..N+M+2 行: 两个整数: i , j, 表示已经存在从农场i到农场j的路。

输出

* 第 1 行: 额外的路的最少长度,保留2小数。 请使用 64 位的浮点数。

样例输入
Copy
 4 1
 1 1
 3 1
 2 3
 4 3
 1 4
样例输出
Copy
 4.00

提示

来源

 

[提交][状态]