LQDXEUI - 2 xe ủi
Giới hạn- Thời gian: 0.129s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Một thành phố gồm n địa điểm và n-1 con đường nối chúng .Từ mỗi địa điểm có thể đi đến các địa điểm còn lại qua đúng 1 tuyến đường.
Mùa đông,các con đường bị phủ bởi lớp tuyết rất dày nên giao thông bị tắc nghẽn.Ngài thị trưởng thành phố đã cho 2 xe ủi để ủi tuyết.
Ban đầu 2 xe đứng ở địa điểm X. Chi phí di chuyển trên con đường đúng bằng độ dài con đường đó . Một con đường được ủi nếu có ít nhất con xe di chuyển qua con đường đó .Hai xe sẽ dừng lại nếu tất cả các con đường đã được ủi.
Yều cầu: Tìm cách ủi sao cho tổng chi phí nhỏ nhất
Input
Dòng đầu chứa số nguyên N và X (N <= 10 5 )
N-1 tiếp theo, mỗi dòng chứa ba số nguyên u, v và t có nghĩa có tuyến đường nối 2 địa điểm u và v với chi phí t (t <= 10 3 )
Output
Xuất ra tổng chi phí nhỏ nhất
Example
Input: 4 1 1 3 2 1 2 3 1 4 4 Output: 11
Input: 6 1 1 2 1 2 3 1 1 4 1 4 5 1000 4 6 1000 Output: 2006
Ở ví dụ 1 : xe 1 di chuyển sang địa điểm 3 rồi sang lại địa điểm 1
(chi phí = 2+2).
Sau đó xe 1 sang địa điểm 2 ,xe 2 sang địa điểm 4 (chi phí =3+4)
Tổng chi phí là 2+2+3+4=11
Ở ví dụ 2 : xe 1 di chuyển sang địa điểm 2 rồi sang địa điểm 3,
sau đó sang lại địa điểm 2 rồi sang lại địa điểm 1.(chi phí = 1+1+1+1)
Sau đó 2 xe cùng di chuyển sang địa điểm 4 (chi phí = 1+1)
Rồi xe 1 di chuyển sang địa điểm 5 và xe 2 di chuyển
sang địa điểm 6 (chi phí = 1000+1000)
Tổng chi phí = 1+1+1+1+1+1+1000+1000=2006
- Người up: kauke