Code Submission Evaluation System Login

BOI 2016, day 2

Start:2016-05-13 09:00:00
End:2016-05-13 14:00:00

Tasks | Scoreboard | Statistics

CSES - BOI 2016, day 2 - CitiesCSES - Cities


Time limit:2.00 s
Memory limit:256 MB

There are $n$ cities in Byteland, and $k$ of them are important cities frequently visited by the king of Byteland.

There are also $m$ roads in the country, each of them connecting two cities. Unfortunately, the condition of the roads is so bad that the king cannot drive through them at full speed with his sports car.

For each road, the cost for renovating it is known. Your task is to choose which roads will be renovated so that all $k$ important cities are connected with renovated roads, and the total cost is as low as possible.


The first input line contains three integers $n$, $k$ and $m$: the number of cities, the number of important cities and the number of roads. The cities are numbered $1,2,\ldots,n$. The second input line contains $k$ integers: the important cities.

Finally, the input contains $m$ lines that describe the roads. Each line contains three integers $a$, $b$ and $c$, meaning that there is a bidirectional road between cities $a$ and $b$, and the renovation cost for the road is $c$.

You may assume that there is a route between any two cities.


You should output the minimum total cost for renovating the roads so that the king can travel between all important cities with his sports car.


4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8



In all subtasks $1 \le c \le 10^9$ and $n \ge k$.

Subtask 1 (22 points)
Subtask 2 (14 points)
Subtask 3 (15 points)
Subtask 4 (23 points)
Subtask 5 (26 points)