P2914 [USACO08OCT] Power Failure G

一场猛烈的雷暴摧毁了农场电力网的一些电线！农夫约翰有一张所有 $N$ 根电线杆的地图（$2 \le N \le 1000$），这些电线杆被方便地编号为 $1\ldots N$，并位于整数平面坐标 $(x_i, y_i)$ 上（$-100000 \le x_i \le 100000, -100000 \le y_i \le 100000$）。 有 $W$ 根电线（$1 \le W \le 10000$）连接成对的电线杆 $P_i$ 和 $P_j$（$1 \le P_i \le N, 1 \le P_j \le N$）。 他需要从电线杆 $1$ 获取电力到电线杆 $N$（这意味着一些电线可以从电线杆 $1$ 通过某些中间电线杆传输到电线杆 $N$）。 给定 $N$ 根电线杆的位置和剩余电线的列表，确定恢复电力连接所需的最小电线长度，以便电力可以从电线杆 $1$ 流向电线杆 $N$。没有电线可以长于某个实数 $M$（$0.0 < M \le 200000.0$）。 例如，下面左侧是暴风雨后 $9$ 根电线杆和 $3$ 根电线的地图。对于这个任务，$M = 2.0$。最佳的电线连接方案是连接电线杆 $4$ 和 $6$，以及电线杆 $6$ 和 $9$。 ```cpp 暴风雨后 最优重新连接 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

第 $1$ 行：两个用空格分隔的整数：$N$ 和 $W$。 第 $2$ 行：一个实数：$M$。 第 $3\ldots N+2$ 行：每行包含两个用空格分隔的整数：$x_i$ 和 $y_i$。 第 $N+3\ldots N+2+W$ 行：两个用空格分隔的整数：$P_i$ 和 $P_j$。

第 1 行：单独一行上的一个整数。如果无法恢复连接，输出 `-1`。否则，输出一个整数，该整数是恢复电力所需的总最小成本的 $1000$ 倍。不要进行任何四舍五入；截断结果乘积。

就像上面的图示一样。 如上所述。 （由 ChatGPT 4o 翻译）