2 xe ủi

View as PDF

Submit solution


Points: 0.45 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 \leq 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 \leq 10^{3})~

Output

  • Xuất ra tổng chi phí nhỏ nhất

Sample Input 1

4 1
1 3 2
1 2 3
1 4 4

Sample Output 1

11

Sample Input 2

6 1
1 2 1
2 3 1
1 4 1
4 5 1000
4 6 1000

Sample Output 2

2006

Note

  • Ở 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~

Comments

Please read the guidelines before commenting.


There are no comments at the moment.