Tưới Ruộng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $N$ cánh đồng trên mặt phẳng tọa độ, cánh đồng thứ $i$ nằm ở vị trí $(x_{i}, y_{i})$ . Chi phí để xây đường ống nối cánh đồng $i$ và $j$ bằng khoảng cách Euclid bình phương: $(x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}$ .

Tuy nhiên, nhà thầu chỉ chấp nhận xây các đường ống có chi phí ít nhất $C$ .

Hãy tìm tổng chi phí nhỏ nhất để kết nối tất cả các cánh đồng, hoặc in $- 1$ nếu không thể.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $C$ .
$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ và $y_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất — tổng chi phí nhỏ nhất để kết nối tất cả cánh đồng, hoặc $- 1$ nếu không thể.

Ràng buộc

$1 \leq N \leq 2000$
$1 \leq C \leq 1 000 000$
$0 \leq x_{i}, y_{i} \leq 1000$

Ví dụ

Input	Output	Giải thích
3 11 0 2 5 0 4 3	46	Đường ống giữa $(4, 3)$ và $(5, 0)$ có chi phí $10 < C = 11$ nên không được xây. Xây hai đường ống còn lại: chi phí $29$ và $17$ , tổng $= 46$ .

Bình luận

Không có bình luận tại thời điểm này.