URAL 1982. Electrification Plan

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1982

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.

Input

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

Output the minimum cost to electrify all the cities.

Sample

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

2. 思路

给出n个城市两两之间建设输电线的费用,和k个建有发电站的城市,求将所有城市通上电(与建有发电站的城市间建设输电线)的最小费用。

求无向带权图的最小生成树。题目输入直接是图的邻接矩阵,直接使用很方便。开始给出的k个建有发电站的城市,看做已经相互连通,在此基础上求最小生成树。

下面的代码使用Prim算法求最小生成树。

3. 代码