Problem S
Building Highways
The country of Singanesia consists of
-
They will build several highways such that from any city, someone can go to any other cities using the built highways
-
They will minimize the sum of the difficulty level of building the intercities highways
As the leader for this development plan, your task is to find the minimum sum of the difficulty level to build the intercities highways.
Input
The first line contains an integer
The next line contains
Output
Output the minimum sum of the difficulty level to build the highways.
Subtasks
-
(
Points): . -
(
Points): All have the same value. -
(
Points): No additional constraints.
Explanation
Below is the explanation for the first sample. Each line denotes the difficulty of building the highway. The red lines denote one possible intercities highways plan with the minimum sum of the difficulty level.
![\includegraphics[width=0.6\textwidth ]{sample1.png}](/problems/buildinghighways/file/statement/en/img-0001.png)
Below is the explanation for the second sample.
![\includegraphics[width=0.6\textwidth ]{sample2.png}](/problems/buildinghighways/file/statement/en/img-0002.png)
Sample Input 1 | Sample Output 1 |
---|---|
4 2 3 2 5 |
16 |
Sample Input 2 | Sample Output 2 |
---|---|
5 3 1 7 5 1 |
20 |