Hai con tàu
Đề bài
Mô tả
Một công ty được giao nhiệm vụ thu gom khoáng sản từ mỏ nằm ở các tọa độ cho trước trên biển. Mỗi mỏ có đúng tấn khoáng sản. Ngoài ra có hai hòn đảo và , mỗi đảo nằm ở một tọa độ cho trước.
Công ty có hai con tàu:
- Một tàu xuất phát từ đảo và phải quay về đảo .
- Tàu còn lại xuất phát từ đảo và phải quay về đảo .
Mỗi tàu chở được lượng khoáng sản không giới hạn và có thể ghé nhiều mỏ theo thứ tự bất kỳ. Tuy nhiên, mỗi tàu chỉ được rời đảo và quay về đúng một lần.
Khi một tàu di chuyển từ địa điểm này sang địa điểm khác (giữa một mỏ và một đảo, hoặc giữa hai mỏ), tàu tiêu tốn nhiên liệu. Lượng nhiên liệu cho một lần di chuyển là:
(Số tấn khoáng sản đang có trên tàu) (khoảng cách Manhattan giữa hai địa điểm)
Khoảng cách Manhattan giữa hai điểm và là . Khi bắt đầu hành trình (rời đảo), mỗi tàu chở tấn, nên lần di chuyển đầu tiên không tốn nhiên liệu.
Yêu cầu: Phân mỗi mỏ cho một trong hai tàu và xác định lộ trình của mỗi tàu (bắt đầu và kết thúc ở đảo của nó) sao cho thu gom được toàn bộ tấn khoáng sản và tổng nhiên liệu của cả hai tàu là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : số mỏ.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên , : tọa độ mỏ thứ .
- Dòng tiếp theo chứa hai số nguyên , : tọa độ đảo .
- Dòng cuối cùng chứa hai số nguyên , : tọa độ đảo .
Dữ liệu ra
In ra một số nguyên là tổng nhiên liệu nhỏ nhất cần dùng để thu gom toàn bộ khoáng sản và mang về các đảo.
Ràng buộc
- Mọi tọa độ đều phân biệt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 1 2 2 3 3 0 0 4 4 |
8 | Tàu : , tốn . Tàu : , tốn . Tổng . |
| 4 5 0 6 0 -5 0 -6 0 0 0 10 10 |
40 | Ví dụ bổ sung (không có trong đề gốc). Tàu : , tốn . Tàu : , tốn . Tổng ; một mình tàu gom cả bốn mỏ tốn ít nhất . |
Bình luận