URAL 1982. Electrification Plan

1. 题目


1982. Electrification Plan

Time limit: 0.5 second
Memory limit: 64 MB
Some country has n cities. The government has decided to electrify all these cities. At first, power stations in k different cities were built. The other cities should be connected with the power stations via power lines. For any cities i, j it is possible to build a power line between them in cij roubles. The country is in crisis after a civil war, so the government decided to build only a few power lines. Of course from every city there must be a path along the lines to some city with a power station. Find the minimum possible cost to build all necessary power lines.


The first line contains integers n and k (1 ≤ kn ≤ 100). The second line contains k different integers that are the numbers of the cities with power stations. The next n lines contain an n × n table of integers {cij} (0 ≤ cij ≤ 105). It is guaranteed thatcij = cji, cij > 0 for ij, cii = 0.


Output the minimum cost to electrify all the cities.


input output
Problem Author: Mikhail Rubinchik
Problem Source: Open Ural FU Championship 2013

2. 思路




3. 代码