Description
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 ≤ 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 { cij} (0 ≤ cij ≤ 10 5). It is guaranteed that cij = cji, cij > 0 for i ≠ j,cii = 0.
Output
Output the minimum cost to electrify all the cities.
Sample Input
| input | output |
|---|---|
4 2 1 4 0 2 4 3 2 0 5 2 4 5 0 1 3 2 1 0 |
3 |
int n,m; struct Edge { int from,to,cost; }; int p[maxn]; int find(int x) { if(x == p[x]) return x; else { p[x] = find(p[x]); return p[x]; } } vector<Edge> edges; bool cmp(Edge e1,Edge e2) { return e1.cost < e2.cost; } int kruskal() { int ans = 0; rep(i,0,edges.size()) { int x = find(edges[i].from); int y = find(edges[i].to); if(x != y) { p[x] = y; ans += edges[i].cost; } } return ans; } int main() { //freopen("in.txt","r",stdin); while(cin>>n>>m) { int b; cin>>b; repf(i,1,n) p[i] = i; repf(i,2,m) { int a; scanf("%d",&a); p[a] = b; } edges.clear(); repf(i,1,n) repf(j,1,n) { int a; scanf("%d",&a); if(i < j) edges.push_back((Edge){i,j,a}); } sort(edges.begin(),edges.end(),cmp); cout<<kruskal()<<endl; } return 0; }