188. [USACO Oct08] 被破坏的电力系统

【题目描述】

一场邪恶的暴风雨毁坏了农夫约翰的输电网中的一些电线！农夫约翰有一张包含了所有n（2<=n<=1000）个电能中转点的地图，这些 点被很自然而方便的标识为1..n，并且被整数坐标x_i，y_i（-100000<=x_i<=100000;-100000& lt;=y_i<=100000）定位于坐标系。

有w（1<=w<=10000）条电线仍然保存着没被暴风雨破坏，每条电线连接着两个电能中转点pi,pj（1<=pi<=n;1<=pj<=n）。

他希望从第一个电能中转点把电导入第n个（可能通过一些中间的电能中转点，应当有一组电线连接1和n）。

给出n个电能中转点的坐标和幸存的电线，请确定最少需要架设的电线总长度，但请注意，架设过程中，对于单条电线而言，其长度不应超过m（0.0<=m<=200000.0）

给出一个例子，在下面，左边是一个包含9个电能中转电和3条幸存电线的地图。在这个任务中，规定名。m=2.0。最佳的架设方案是连接6和4，以及6和9。

   After the storm              Optimally reconnected
3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                            /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                          /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                                |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

这是的总长度是 1.414213562 + 1.414213562 = 2.828427124 .

【输入格式】

第一行：两个用空格隔开的整数 n和w

第二行：一个实数：m

第3..n+2：每一行包含两个用空格隔开的整数：x_i和y_i

第n+3..n+2+w行：两个空格隔开的整数：pi和pj

【输出格式】

第一行：一个整数，实际结果乘以1000后取整。请不要进行任何的4舍5入工作。

【输入样例】

9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4

【输出样例】

2828