COCI 2019/2020 - Contest 5 - Putovanje
Xem dạng PDFChàng Fabijan rất thích đi bar và đi du lịch. Anh ấy mong muốn rằng mình có thể được trải nghiệm beer cà phê ở tất cả các thị trấn tại quốc gia của mình. Có ~N~ thị trấn được đánh số từ ~1~ đến ~N~. Các thị trấn được nối với nhau bằng các tuyến đường hai chiều. Có tất cả ~(N-1)~ con đường hai chiều sao cho từ một thị trấn ta có thể đi đến bất kì thị trấn khác bằng cách đi qua một số con đường.
Fabijan đã quyết định sẽ lên đường để trải nghiệm tất cả cà phê tại các thị trấn theo thứ tự từ ~1~ đến ~N~. Anh ấy khởi đầu tại thị trấn có số thứ tự là ~1~ (nơi mà anh ấy đã uống cốc cà phê đầu tiên) và sẽ hướng đến thị trấn số ~2~ để trải nghiệm cốc cà phê tiếp theo. Trên đường đi đến thị trấn tiếp theo Fabijan có thể đi qua một số thị trấn khác nhau nhưng anh ấy sẽ chỉ dừng lại khi đến được thị trấn thứ ~2~. Sau khi đến được thị trấn thứ ~2~, anh ta sẽ lại tiếp tục đi cho đến khi đến được thị trấn thứ ~3~, cứ như vậy cho đến khi anh ấy đến được thị trấn ~N~ và thưởng thức tách cà phê cuối cùng.
Tuy nhiên, để vượt qua được những con đường, Fabijan sẽ cần có những tấm vé thông hành. Để đi qua một con đường ~i~, Fabijan có thể lựa chọn một trong hai cách:
- Cách 1: mua vé dùng một lần giá ~C_{i1}~ euro để đi qua con đường đó một lần.
- Cách 2: mua vé dùng nhiều lần giá ~C_{i2}~ euro một lần duy nhất và khi gặp lại con đường đó sẽ không cần mua vé nữa.
Hãy viết chương trình xác định số tiền nhỏ nhất mà Fabijan phải bỏ ra để hoàn thành chuyến đi của mình.
Input
- Dòng đầu chứa số nguyên ~N~ (~2 \leq N \leq 200000~).
- ~(N-1)~ dòng tiếp theo mỗi dòng gồm 4 số nguyên ~A_i~ ~B_i~ ~C_{i1}~ ~C_{i2}~ ~(1 \leq A_i, B_i \leq N, 1 \leq C_{i1} \leq C_{i2} \leq 100000 )~ biểu diễn một đường đi giữa hai thành phố ~A_i~ và ~B_i~ với giá vé dùng một lần là ~C_{i1}~ và giá vé dùng nhiều lần là ~C_{i2}~.
Output
- Số tiền nhỏ nhất mà Fabijan phải bỏ ra cho chuyến đi
Sample 1
Input
4
1 2 3 5
1 3 2 4
2 4 1 3
Output
10
Sample 2
Input
4
1 4 5 5
3 4 4 7
2 4 2 6
Output
16
Sample 3
Input
5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3
Output
11
Subtask
- ~9~ test có ~2 \leq N \leq 2000~
- ~12~ test tiếp theo mỗi thị trấn sẽ được kết nối trực tiếp với nhiều nhất hai thị trấn khác.
- ~10~ test còn lại không có điều kiện gì thêm
Giải thích ví dụ thứ nhất
Ta mô tả chuyến đi của Fabijan như sau:
- Đi từ thị trấn 1 đến thị trấn 2: mua vé dùng nhiều lần (5 euro).
- Đi từ thị trấn 2 sang thị trấn 3: từ thị trấn 2 quay về thị trấn 1 (không mất phí vì đã mua vé dùng nhiều lần) rồi mua vé dùng một lần từ thị trấn 1 sang thị trấn 3 (2 euro).
- Đi từ thị trấn 3 đến thị trấn 4: từ thị trấn 3 mua vé dùng một lần để đến thị trấn 1 (2 euro) rồi sang thị trấn 2 (không mất phí vì đã mua vé dùng nhiều lần) và mua vé dùng một lần sang thị trấn 4 (1 euro)
Tổng số tiền mà Fabijan bỏ ra là 5 + 2 + 2 + 1 = 10
Bình luận
solve:
Spoil
ggez