Bedao Mini Contest 26 - Hướng dẫn viên
Xem dạng PDF
Bạn Phương là một hướng dẫn viên du lịch tại đất nước ~X~ có ~N~ thành phố và ~N - 1~ tuyến đường hai chiều, tuyến đường thứ ~i~ có độ dài ~w_i~ nối liền hai thành phố ~u_i~ và ~v_i~. Dữ liệu luôn đảm bảo tồn tại hành trình di chuyển giữa bất kì cặp thành phố nào.
Bạn Phương được chọn một thành phố ~S~ để bắt đầu hành trình, sau đó ghé thăm ~N - 1~ thành phố còn lại, mỗi thành phố đúng một lần, rồi quay trở lại thành phố ~S~ và kết thúc chuyến du lịch. Khi đang ở một thành phố ~u~, bạn Phương có thể thực hiện một trong hai hành động sau:
Ghé thăm thành phố ~v~ kề với ~u~ thông qua tuyến đường nối hai thành phố đó. Chi phí của hành động này là ~A \cdot w~ với ~w~ là độ dài của tuyến đường.
Ghé thăm thành phố ~v~ bất kì bằng cách dịch chuyển tức thời đến thành phố đó. Chi phí của hành động này là ~B~.
Yêu cầu: Tính tổng chi phí tối thiểu để thực hiện chuyến du lịch.
Input
Dòng đầu tiên gồm ba số nguyên ~N, A, B~ (~2 \le N \le 200000~; ~1 \le A, B \le 10^9~) – lần lượt là số thành phố và các chi phí để thực hiện hành động.
~N - 1~ dòng tiếp theo gồm các số nguyên ~u_i~, ~v_i~, ~w_i~ (~1 \le u_i, v_i \le N~; ~u_i \neq v_i~; ~1 \le w_i \le 10^9~) – tuyến đường thứ ~i~ nối liền hai thành phố ~u_i~ và ~v_i~, có độ dài là ~w_i~.
Output
Một số nguyên duy nhất là chi phí tối thiểu để thực hiện chuyến du lịch.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~n \le 9~ |
| 2 | ~20~ | ~n \le 16~ |
| 3 | ~20~ | Đồ thị có dạng đường thẳng |
| 4 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
5 9 10
1 4 2
4 5 5
2 5 3
5 3 4
Sample Output 1
50
Sample Input 2
5 2 10
1 4 2
4 5 5
2 5 3
5 3 4
Sample Output 2
38
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài y hệt: FC 100 TREETRIP