Putovanje
레이팅 미적용의견: 0
Little Fabijan loves bars and travels. He wishes to drink beer coffee in each of the \(N\) towns in his country
conveniently numbered from 1 to \(N\). The towns are connected via (\(N - 1\)) bidirectional roads such that
each town is reachable from any other town by traversing some of the roads. Fabijan decided to drink
coffee in every town in order from town number 1 to town number \(N\). Therefore, he starts from town
number 1 (where he drinks his first coffee) and travels to town number 2 for his next cup of coffee. During
that travel he might pass through a number of different towns but he won’t make a coffee stop in those
towns. After drinking coffee in town 2, he will proceed to travel to town 3, and so on until he finally
reaches town \(N\) where he will drink his last coffee.
In order to traverse a certain road, he needs to have a valid ticket. The \(i-th\) road can be traversed if you
have either a sing\(le-pa\)ss ticket which costs \(C@@RISE_MATH_BLOCK_0@@i\)2 euros. For
each road, Fabijan can decide to buy a sing\(le-pa\)ss ticket each time he needs to traverse that road or he
might opt to buy a mul\(ti-pa\)ss ticket once.
Write a program that computes the smallest number of euros Fabijan needs to spend on tickets in order
to successfully complete his travels.
Subtask
Score
Constraints
1
20
\(2 \le N \le 2000\)
2
25
Each town will be directly connected with at most two other towns.
3
65
No additional constraints.
The first line contains an integer \(N\) (\(2 \le N \le 200\,000\)) from task description.
In \(i-th\) of the next (\(N - 1\)) lines there are four integers \(A_{i}\), \(B_{i}\), \(C_{i}\){1}, \(C_{i}\) (\(1 \le A_{i}\), \(B_{i} \le N\), \(1 \le C_{i}\){1} ≤\(C_{i}\) ≤
100 000) which represent that towns \(A_{i}\) and \(B_{i}\) are connected with a road with ticket prices \(C_{i}\){1} and \(C_{i}\).
In a single line output the smallest cost of travel.
4
1 2 3 5
1 3 2 4
2 4 1 3104
1 4 5 5
3 4 4 7
2 4 2 6165
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 311Clarification of the first example:
Fabijan first travels from town 1 to town 2 and it is optimal for him to buy a multi-pass ticket (5 euros)
for the road which connects them. Then he travels from town 2 to town 3 via town 1. He already has a
multi-pass ticket that takes him from 2 to 1 and he buys a single-pass ticket from town 1 to town 3 (2
euros). On his travels from town 3 to town 4 he buys another single-pass ticket that takes him from town
3 back to town 2 (2 euros) and after that buys a single-pass ticket that takes him from town 2 to town 4
(1 euro). In total, he spent 5 + 2 + 2 + 1 = 10 euros.
평가 및 의견
Putovanje
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Putovanje