Metro và xe buýt
Đề bài
Mô tả
Thành phố Hồ Chí Minh đã xây dựng một hệ thống metro. Hệ thống gồm ga và tuyến metro hai chiều. Tuyến thứ nối hai ga và , có giá vé .
Biết rằng có thể đi từ một ga bất kỳ đến mọi ga khác (có thể phải chuyển tuyến), và giá của một lộ trình gồm nhiều tuyến liên tiếp bằng giá vé của tuyến đắt nhất trong đó. Cụ thể hơn, giá của lộ trình từ ga đến ga với lần chuyển tuyến tại các ga bằng giá lớn nhất trong các tuyến từ đến , từ đến , ..., từ đến .
Hôm nay, chính quyền quyết định xây các tuyến xe buýt (cũng hai chiều) cho mọi cặp ga không được nối trực tiếp bằng tuyến metro. Như vậy, giữa mọi cặp ga có đúng một tuyến trực tiếp: hoặc metro, hoặc xe buýt.
Giá vé xe buýt được tính như sau: với mỗi cặp ga và được nối bằng tuyến xe buýt, giá của tuyến này bằng giá nhỏ nhất của một lộ trình metro từ đến theo cách tính giá ở trên.
Biết rằng chỉ dùng các tuyến xe buýt cũng có thể đi từ một ga bất kỳ đến mọi ga khác, và tương tự như metro, giá của một lộ trình gồm nhiều tuyến xe buýt bằng giá của tuyến đắt nhất trong đó.
Do sự cạnh tranh ngày càng tăng từ hệ thống xe buýt, ban quản lý metro đưa ra một cải cách và thay đổi giá vé các tuyến metro. Cụ thể, với tuyến metro thứ nối hai ga và , giá mới của tuyến này bằng giá nhỏ nhất của một lộ trình xe buýt giữa hai ga và . Hãy giúp ban quản lý metro tính giá mới của các tuyến metro.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên (): số bộ test.
- Dòng đầu tiên của mỗi bộ test chứa hai số nguyên và : số ga và số tuyến metro (, , ).
- Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và (, ): hai ga được nối bởi tuyến metro thứ và giá vé của tuyến đó.
Dữ liệu đảm bảo không có tuyến nào nối một ga với chính nó, không có hai tuyến nối cùng một cặp ga, chỉ dùng metro có thể đi giữa mọi cặp ga, và chỉ dùng xe buýt cũng có thể đi giữa mọi cặp ga.
Gọi là tổng các và là tổng các của mọi bộ test. Dữ liệu đảm bảo .
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng số nguyên, số thứ là giá mới của tuyến metro thứ sau cải cách.
Ràng buộc
- , ,
- Tổng và tổng của mọi bộ test không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 3 1 2 1 2 3 2 4 3 3 5 5 1 2 1 1 3 1 2 4 1 4 5 2 5 1 3 6 6 1 2 3 2 3 1 3 6 5 3 4 2 4 5 4 2 4 2 |
3 3 3 1 1 1 2 2 4 4 5 3 4 4 |
Bộ test thứ nhất: các tuyến xe buýt là giá (lộ trình metro ), giá và giá . Sau cải cách, tuyến metro có giá (xe buýt ), tuyến có giá (xe buýt ), tuyến có giá (xe buýt ). Bộ test thứ hai: các tuyến xe buýt là giá , giá , giá , giá , giá . |
Bình luận