Trà sữa
Đề bài
Mô tả
Suika là một fan cuồng của trà sữa Đài Loan, ngày nào cô bé cũng có thể uống một cốc lớn, có hôm còn uống hai cốc. Sau năm học vừa qua, Suika được trao danh hiệu học sinh có thành tích cao nhất toàn trường. Để chúc mừng thành tích này, bố mẹ quyết định tặng cô bé một chuyến du lịch Đài Loan để cô bé thoải mái thư giãn và chuẩn bị cho năm học mới.
Dĩ nhiên Suika định uống thật nhiều trà sữa khi ở Đài Loan. Chỉ thử vài cốc thì chưa đủ: sau một thời gian suy nghĩ, cô bé nói với bố mẹ rằng mình sẽ uống trà sữa ở mọi thị trấn mình đi qua. Cô bé cũng có một kế hoạch rất rõ ràng về các thị trấn sẽ ghé thăm. Nhưng Suika vẫn chỉ là một cô bé, và đây là lần đầu cô bé đi nước ngoài mà không có bố mẹ, nên Suika chỉ ghi nhớ một danh sách ngắn nhất các con đường để đi lại giữa các thị trấn đó. Giả sử có thị trấn cô bé muốn ghé thăm, cho đơn giản cô bé chỉ biết con đường hai chiều (các con đường này nối tất cả các thị trấn với nhau). Cô bé đánh số các thị trấn từ tới và quyết định ghé thăm chúng theo thứ tự từ tới . Nghĩa là cô bé sẽ đến thị trấn và uống một cốc trà sữa, đi tham quan, rồi đến thị trấn và lại uống trà sữa, cứ thế tiếp tục.
Để đi qua một tuyến đường cụ thể, cô bé cần có vé tàu hợp lệ. Với tuyến tàu thứ có loại vé: vé một lượt có giá đô la Đài Loan và vé nhiều lượt có giá đô la. Với mỗi tuyến, cô bé có thể chọn mua một vé một lượt mỗi lần cần đi qua tuyến đó, hoặc mua một vé nhiều lượt duy nhất một lần.
Hãy giúp Suika tìm số đô la Đài Loan nhỏ nhất cô bé cần chi để tận hưởng trọn vẹn chuyến đi.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên ().
- dòng tiếp theo, mỗi dòng chứa số nguyên (, ): thị trấn và được nối bởi một tuyến tàu với giá vé một lượt và giá vé nhiều lượt .
Dữ liệu ra
In ra một dòng duy nhất là chi phí nhỏ nhất cho chuyến đi.
Ràng buộc
- tuyến tàu nối tất cả các thị trấn với nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 1 2 1 3 1 3 1 4 2 4 2 3 3 5 2 3 |
11 | Suika đi qua tuyến lần lượt lần. Cô bé mua vé nhiều lượt cho tuyến và , vé một lượt cho tuyến và . Chi phí: . |
| 5 1 2 3 5 1 3 2 3 1 4 1 3 1 5 2 3 |
12 | Các tuyến được đi qua lần lượt lần. Chi phí: . |
Bình luận