Mất điện

View as PDF

Submit solution


Points: 0.19 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO October 2008 - Qualifying Round
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một cơn bão đã phá hủy một số đường dây điện của nông trang! Nông dân John có một bản đồ tất cả ~N~ ~(2 \le N \le 1000)~ cây cột điện, để thuận tiện ta đánh số các cột này từ ~1 \rightarrow N~, mỗi cột này được xác định trên mặt phẳng bởi ~2~ số nguyên ~x_i, y_i~ ~(-100000 \le x_i \le 100000~; ~-100,000 \le y_i \le 100000)~.

Hiện đang có ~W~ ~(1 \le W \le 10000)~ đường dây điện nối các cặp cột điện ~P_i~ và ~P_j~ ~(1 \le P_i \le N;~ ~1 \le P_j \le N)~. John cần mang điện từ cột ~1~ tới cột ~N~ (thông qua các đường dây điện và các cột điện khác).

Cho tọa độ của ~N~ cột điện và danh sách những đường dây điện vẫn còn hoạt động. Hãy xác định độ dài nhỏ nhất của các đường dây điện cần thêm để sao cho điện từ cột ~1~ có thể truyền tới cột ~N~. Biết rằng độ dài tối đa của ~1~ đường dây điện là ~1~ số thực ~M~ ~(0.0 \le M \le 200000.0)~.

Ví dụ, dưới đây là bên trái là bản đồ ~9~ cột điện và ~3~ dây nối vẫn còn hoạt động sau cơn bão. Trong ví dụ này, ~M = 2~. ~0~. Cách tốt nhất là ta thêm ~2~ đường dây điện nối ~4-6~ và ~6-9~.

      Sau cơn bão                   Phương án tối ưu

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

Tổng độ dài là ~1~. ~414213562~ + ~1~. ~414213562 = 2~. ~828427124~.

Input

  • Dòng ~1~: Hai số nguyên cách nhau bởi dấu cách: ~N~ và ~W~
  • Dòng ~2~: Một số thực: ~M~
  • Dòng ~3..N+2~: Mỗi dòng gồm ~2~ số nguyên cách nhau bởi dấu cách: ~x_i~ và ~y_i~
  • Dòng ~N+3..N+2+W~: ~2~ số nguyên cách nhau bởi dấu cách: ~P_i~ và ~P_j~

Output

  • Dòng ~1~: Một số nguyên trên ~1~ dòng. Nếu không có phương án để cấp điện cho cột ~N~ từ cột ~1~ thì ghi ra ~-1~. Ngược lại, ghi ra ~1~ số nguyên là tổng độ dài nhỏ nhất nhân với ~1000~.
  • Chú ý không làm tròn, làm giảm tích thu được ở trên.

Sample Input

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

Sample Output

2828

Comments

Please read the guidelines before commenting.


There are no comments at the moment.