Not enough electricity
Time limit1sMemory limit256 MB
Connect every city to exactly one of the given power plants with minimum total cable cost.
- Level
Medium5 of 10
- Topics
- Minimum spanning tree, Union-find
- Solved
- No attempts yet
Problem
Seogang leads in both software and hardware, so people call it an IT powerhouse. It has been ranked the best country to live in since 2015, and the number of foreign visitors has grown a lot since then. Electricity consumption grew with them, and the whole country is now short of power.
The president decided to start the YNY power plant project, whose development just finished. The plant buildings already stand in certain cities, so the only extra cost is the cost of laying cables between cities. Cables are expensive, so the total cost has to be as small as possible while every city receives electricity.
There are cities, cables that can be installed, and cities that hold a plant. A city drawing electricity from two plants at once wastes power, so every group of cities joined by cables must contain exactly one plant. A city that holds a plant powers itself even when no cable reaches it.
Choose the cables to install and report the minimum total cost of supplying every city.
Input
The first line contains the number of cities (), the number of cables that can be installed (), and the number of power plants ().
The second line contains the numbers of the cities that hold a plant. The numbers are distinct.
Each of the next lines contains one cable as , , . Installing the cable between city and city costs . is a positive integer no greater than .
A way to supply every city always exists.
Output
Print on one line the minimum cost of installing cables so that every city receives electricity.