Codeforces Round #803 (Div. 2)
00:26:54 |
Codeforces Round #804 (Div. 2)
7 өдрийн дараа |
E. Агуа Шаасс
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Агуа Шаасс бол бол Драхт эзэнт гүрний шинэ хаан юм. Эзэнт гүрэн нь $n$ хоттой ба хотууд $n-1$ хоёр чиглэлт замаар холбогдсон. Бүх замууд тодорхой урттай ба хос хотыг холбодог.
Сүр хүчит агуа Шаасс нэг замыг нурааж яг тийм урттай замыг өөр хотуудын дунд барихаар шийджээ. Тэрээр дурын $2$ хотын хооронд зорчиж болохоор барих ёстой. Тэрээр өмнөх замаа дахин тавьсан ч болно.
Та түүний зөвлөгч бөгөөд бүх хот хоорондын замын нийлбэр нь хамгийн бага байхаар замыг тавина уу. Мөн уг нийлбэрийг олно уу.
Оролт
Эхний мөрөнд эзэнт гүрэнд байх хотын тоо $n$ ($2 ≤ n ≤ 5000$) байна. Дараагийн $n-1$ мөрөнд $a_i$, $b_i$, $w_i$ тоонууд байх ба $a_i$, $b_i$ хотын хооронд $w_i$ урттай зам байгааг илтгэнэ ($1 ≤a_i, b_i ≤ n$, $a_i ≠ b_i$, $1 ≤ w_i ≤ 10^6$).
Гаралт
Бүх хотын хоорондох зай нь хамгийн бага байх нийлбэрийг ол.
C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.
Орчуулсан: Говьхүү
Жишээ тэстүүд
Оролт
3 1 2 2 1 3 4
Гаралт
12
Оролт
6 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1
Гаралт
29
Оролт
6 1 3 1 2 3 1 3 4 100 4 5 2 4 6 1
Гаралт
825