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

成绩 0 开启时间 2013年01月21日 星期一 13:20
折扣 0.8 折扣时间 2013年01月21日 星期一 13:20
允许迟交 是 关闭时间 2013年01月21日 星期一 13:20
输入文件 pwrfail.in 输出文件 pwrfail.out

一场邪恶的暴风雨毁坏了农夫约翰的输电网中的一些电线！农夫约翰有一张包含了所有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 .

分数：350

题目名称：pwrfail

输入格式：

  • 第一行：两个用空格隔开的整数 n和w
  • 第二行：一个实数：m
  • 第3..n+2：每一行包含两个用空格隔开的整数：x_i和y_i
  • 第n+3..n+2+w行：两个空格隔开的整数：pi和pj

输入样例（file pwrfail）： 

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

输入说明：

就像图表中说的那样。

输出格式：

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

输出样例（file pwrfail.out）： 

2828