Autići
레이팅 미적용의견: 0
There are \(n\) friends. Each friend has a remote control toy car and a garage
in which the car is stored. Every friend also has a pack of road parts used to
build the track for the cars. All the road parts in the \(i-th\) friend’s pack have
the same length \(d\)\(i\).
Two different friends \(a\) and \(b\) may connect their garages with a road. To build
this road, they will both take a road part from their pack and join them,
obtaining a road of length \(d_{a} +d_{b}\). Some pairs of friends are going to connect their garages in the described
way, so that everyone’s garages are connected. In other words, starting from any garage it should be
possible to reach any other garage using the roads.
What is the minimum total road length needed to make a road network in which all the garages are
connected?
Subtask 1 (10 points): \(d@@RISE_MATH_BLOCK_0@@n\)
Subtask 2 (20 points): \(1 \le n \le 1000\)
Subtask 3 (20 points): No additional constraints.
The first line contains a positive integer \(n\) (\(1 \le n \le 100\,000\)), the number of friends.
The next line contains \(n\) positive integers \(d@@RISE_MATH_BLOCK_0@@i \le 10^{9}\)), the length of the road parts in the \(i-th\)
friend’s pack.
In the only line print the minimum total road length needed to make all the garages connected.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(d@@RISE_MATH_BLOCK_0@@n\) |
2 | 20점 | \(1 \le n \le 1000\) |
3 | 20점 | No additional constraints. |
1
1003
5 5 5204
7 3 3 524Clarification of the first example:
Since there is only one friend, his garage is already connected to itself, so there is no need for building any
roads.
Clarification of the third example:
If roads are built between friends 1 and 2, 2 and 3, and between 3 and 4, everyone will be connected, and
the total cost will be (7 + 3) + (3 + 3) + (3 + 5) = 24.
평가 및 의견
Autići
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Autići