Cái giá của biển báo tốc độ
Đề bài
Mô tả
Vào năm 3031, ICPC đã trở nên phổ biến tới mức cần xây cả một thị trấn mới để làm chỗ ở cho tất cả các đội tham dự vòng chung kết thế giới. Thị trấn được thiết kế rất đẹp, có đầy đủ một mạng lưới đường. Đáng tiếc là khi lập ngân sách, những người quy hoạch thị trấn đã quên tính chi phí cho các biển báo giới hạn tốc độ. Họ nhờ bạn xác định số tiền bổ sung ít nhất mà họ cần.
Mạng lưới đường của ICPC gồm các con đường, mỗi con đường nối hai giao lộ. Mỗi con đường là đường hai chiều và đã được gán sẵn một giới hạn tốc độ, áp dụng cho cả hai chiều. Để tiết kiệm, người ta đã dùng số con đường ít nhất có thể. Nói cách khác, giữa hai giao lộ bất kỳ có đúng một tuyến đường đi từ giao lộ này tới giao lộ kia.
Biển báo giới hạn tốc độ cần được lắp ở mọi nơi mà giới hạn tốc độ có thể thay đổi đối với một người lái xe đi theo một tuyến đường bất kỳ. Cụ thể hơn: nếu tại một giao lộ có ít nhất hai con đường gặp nhau với giới hạn tốc độ khác nhau, thì mọi con đường đi ra từ giao lộ đó đều cần lắp một biển báo giới hạn tốc độ tại giao lộ đó. Lưu ý rằng có thể có con đường cần hai biển báo, mỗi đầu một biển.
Lắp một biển báo tốn đô la. Ngoài ra, có thể cải tạo chất lượng và độ an toàn của một con đường bất kỳ để tăng giới hạn tốc độ của nó, nhờ đó có thể giảm số biển báo cần lắp. Tăng giới hạn tốc độ của một con đường thêm km/h (cho cả hai chiều) tốn đô la. Để tránh bị phàn nàn, hội đồng thị trấn không cho phép giảm bất kỳ giới hạn tốc độ nào đã được gán.
Hình dưới là mạng lưới đường của cả hai ví dụ, số trên mỗi cạnh là giới hạn tốc độ ban đầu (km/h).
graph weighted 5 4 1 2 10 1 3 5 1 4 7 2 5 9
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và : là số giao lộ, là chi phí lắp một biển báo.
Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và mô tả một con đường: và là hai giao lộ ở hai đầu con đường, là giới hạn tốc độ hiện tại của con đường (km/h).
Dữ liệu ra
In ra chi phí ít nhất để cải tạo các con đường và lắp biển báo giới hạn tốc độ sao cho quy hoạch của thị trấn thỏa mãn mọi quy tắc nêu trên.
Ràng buộc
- , .
- , , .
- Các con đường tạo thành một cây (giữa hai giao lộ bất kỳ có đúng một tuyến đường).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 1 2 10 1 3 5 1 4 7 2 5 9 |
7 | Tăng giới hạn tốc độ của đường - từ lên (tốn ), khi đó tại giao lộ hai con đường đều có giới hạn nên không cần biển báo. Tại giao lộ lắp biển báo cho ba con đường (tốn ). Tổng chi phí . |
| 5 100 1 2 10 1 3 5 1 4 7 2 5 9 |
9 | Biển báo quá đắt, nên tăng giới hạn tốc độ của mọi con đường lên : tốn và không cần biển báo nào. |
Bình luận