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

c

_ij 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 ≤

k ≤

n ≤ 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 {

c

_ij} (0 ≤

c

_ij ≤ 10

⁵). It is guaranteed that

c

_ij =

c

_ji,

c

_ij > 0 for

i ≠

j,

c

_ii = 0.

Output

Output the minimum cost to electrify all the cities.

Sample

input	output
4 21 40 2 4 32 0 5 24 5 0 13 2 1 0	3

Problem Author: Mikhail Rubinchik

【分析】将任意两个带有发电站的城市之间的距离赋为0，然后prim求最小生成树。(这么简单的思路我居然没有想到，还是学长教我的)。

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include