Chinh phục thế giới
Đề bài
Mô tả
Ha ha ha ha!!! Kẻ thù truyền kiếp của bạn, điệp viên đẹp trai lịch lãm Waco Powers, cuối cùng đã sa vào những cái bẫy chết người trong căn cứ núi lửa bí mật của bạn (ít nhất là bạn cho rằng vậy, vì bạn hơi bận nên không tận mắt chứng kiến). Sau bao nhiêu chờ đợi, bạn đã sẵn sàng để CHINH PHỤC THẾ GIỚI!
Không gì có thể cản đường bạn! À, trừ một vấn đề nhỏ về hậu cần. Các đạo quân tàn ác của bạn tuyên bố sẽ không tiếp tục con đường tàn phá không khoan nhượng qua các quốc gia yếu ớt trên thế giới nếu không được trả lương. Không may là bạn đang cạn tiền: một hang ổ núi lửa có nhiều ưu điểm tuyệt vời, nhưng "giá cả phải chăng" không nằm trong số đó. Bạn đã phải rút tiền từ ngân sách đi lại để trả cho đám thuộc hạ vô ơn. Giờ bạn không chắc làm thế nào để thực sự đưa các đạo quân vào vị trí để CHINH PHỤC THẾ GIỚI.
Bạn có bản đồ các quốc gia trên thế giới cùng mọi tuyến vận chuyển hiện có giữa chúng. Mỗi tuyến nối hai quốc gia và có một chi phí cố định cho mỗi đạo quân đi qua nó. Các tuyến được bố trí sao cho giữa hai quốc gia bất kỳ có đúng một cách đi. Bạn biết vị trí hiện tại của từng đạo quân và số đạo quân cần đóng vĩnh viễn tại mỗi quốc gia để khuất phục quốc gia đó. Hãy di chuyển các đạo quân vào vị trí với chi phí nhỏ nhất có thể để bạn có thể CHINH PHỤC THẾ GIỚI.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên : số quốc gia. Tiếp theo là dòng, mỗi dòng chứa ba số nguyên , và , cho biết có một tuyến hai chiều nối quốc gia và quốc gia , chi phí cho mỗi đạo quân đi qua.
Cuối cùng là dòng, dòng thứ chứa hai số nguyên không âm và : hiện có đạo quân ở quốc gia , và cần ít nhất đạo quân ở quốc gia đó trong cấu hình cuối cùng.
Dữ liệu ra
In ra chi phí nhỏ nhất để di chuyển các đạo quân sao cho với mọi , quốc gia có ít nhất đạo quân.
Ràng buộc
- .
- , ; các tuyến tạo thành một cây.
- .
- Tổng số đạo quân không nhỏ hơn và không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 2 5 3 1 5 2 1 5 0 1 3 |
15 | Quốc gia thiếu đạo quân: đưa đạo quân thừa từ quốc gia sang (chi phí ) và đạo quân từ quốc gia qua quốc gia sang (chi phí ). |
| 6 1 2 2 1 3 5 1 4 1 2 5 5 2 6 1 0 0 1 0 2 1 2 1 0 1 0 1 |
9 | Đạo quân ở quốc gia sang quốc gia (chi phí ), một đạo quân từ quốc gia đi (chi phí ). |
Bình luận