Tiếp tế giữa mùa tuyết
Đề bài
Mô tả
Một trận bão mùa đông đã phủ tuyết lên các con đường nối một nhóm làng trên núi. Một đội cứu trợ cần thu gom hàng tiếp tế được cất giữ ở các làng. Để di chuyển giữa các làng, đội dùng một xe ủi tuyết để dọn đường.
Có làng, đánh số từ đến , được nối với nhau bởi con đường hai chiều. Giữa hai làng bất kỳ có đúng một đường đi. Làng đang cất giữ thùng hàng, và mỗi con đường có một độ sâu tuyết đã biết.
Một xe ủi tuyết có sức dọn đi được trên một con đường khi và chỉ khi độ sâu tuyết của con đường đó không vượt quá . Đội có thể ghé thăm bao nhiêu làng tùy ý và dùng mỗi con đường bao nhiêu lần tùy ý. Đội thu được hàng ở mọi làng mà mình ghé thăm, kể cả làng xuất phát, nhưng mỗi thùng hàng chỉ được thu một lần.
Bạn cần trả lời truy vấn. Mỗi truy vấn cho một làng xuất phát và số thùng hàng cần có . Hãy tìm sức dọn không âm nhỏ nhất để đội thu được ít nhất thùng hàng, hoặc cho biết điều đó là không thể.
Các truy vấn độc lập với nhau: việc thu hàng ở một truy vấn không ảnh hưởng tới lượng hàng có sẵn ở các truy vấn khác.
Dữ liệu vào
Dòng đầu tiên gồm hai số nguyên và (): số làng và số truy vấn.
Dòng thứ hai gồm số nguyên (), trong đó là số thùng hàng được cất ở làng .
Mỗi dòng trong dòng tiếp theo gồm ba số nguyên , và (, , ), mô tả một con đường hai chiều nối làng và làng với độ sâu tuyết .
Dữ liệu đảm bảo các con đường nối liền tất cả các làng và giữa hai làng bất kỳ có đúng một đường đi.
Mỗi dòng trong dòng tiếp theo gồm hai số nguyên và (, ), mô tả một truy vấn.
Dữ liệu ra
Với mỗi truy vấn, in ra một dòng chứa sức dọn nhỏ nhất cần thiết để thu được ít nhất thùng hàng khi xuất phát từ làng . Nếu không thể, in ra .
Ràng buộc
- .
- .
- , , ; các con đường tạo thành một cây.
- , trong mỗi truy vấn.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 7 2 0 4 1 3 5 1 2 3 2 3 7 2 4 3 4 5 6 5 6 7 1 2 1 3 1 6 1 7 3 5 2 1 4 16 |
0 3 6 7 7 3 -1 |
Truy vấn 1: làng đã có thùng nên đáp án là . Truy vấn 2: với sức dọn , xuất phát từ làng đội đến được các làng , tổng cộng thùng. Truy vấn cuối: cần thùng nhưng tổng cộng chỉ có thùng nên đáp án là . |
| 4 3 0 2 2 2 1 2 3 1 3 3 1 4 3 1 5 2 2 2 7 |
3 0 -1 |
Truy vấn 1: đội phải ghé cả ba làng có hàng, đi qua làng giữa các lần ghé. Sức dọn là đủ. |
Bình luận