ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

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 that cij = cji, cij > 0 for ij, cii = 0.


Output the minimum cost to electrify all the cities.


4 2
1 4
0 2 4 3
2 0 5 2
4 5 0 1
3 2 1 0
Problem Author: Mikhail Rubinchik
Problem Source: Open Ural FU Championship 2013