Well Project

Level 3
Well Project


Our company planned to help dig a well in a place in Africa which suffers from lack of water.
After lots of research, we could dig the well full of water.
After this success, we decided not only to dig the well but also to connect pipelines to towns scattered far from the well.


Now your task is to connect all towns together with the well with the minimum length of pipelines.
Find out the minimum pipeline length.


Time limit : 1 sec (Java : 2 sec)


[Input]
There can be more than one test case in the input file. The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T ≤ 10 )


In each test case, The size of the matrix (N) is given at the first row. (3 ≤ N ≤ 100)
The distance information of each town is given from the second row to row of N.
The information is the format of N×N matrix. jth number of ith row is the distance from ith town to jth town.
The number on a diagonal line is always 0.


[Output]
For each test case, you should print "Case #T" in the first line where T means the case number. For each test case, you should output the minimum pipeline length to connect each town in the first row.


[I/O Example]

Input
2
3
0 1 4
1 0 2
4 2 0
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0


Output

Case #1
3
Case #2
28

Case #1
3433
Case #2
6043
Case #3
6061
Case #4
5831
Case #5
6922
Case #6
5337
Case #7
5822
Case #8
6070
Case #9
4830
Case #10
5656
#include <iostream>
using namespace std;

int T, n;
long result;
int mp[101][101];
bool vs[101];

void prim(){
	for(int i = 0; i < n; i++) vs[i] = false;
	vs[0] = true;
	int selected = 1;
	while(selected < n){
		int minV = LONG_MAX, minI;
		for(int i = 0; i < n; i++){
			if(vs[i]){
				for(int j = 0; j < n; j++){
					if(!vs[j] && i != j){
						if(minV > mp[i][j]){
							minV = mp[i][j];
							minI = j;
						}
					}
				}
			}
		}
		vs[minI] = true;
		selected++;
		result += minV;
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;

	for(int tc = 1; tc <= T; tc++){
		// Input
		cin >> n;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++)
				cin >> mp[i][j];
		}

		// Initial
		result = 0;

		// Solve Problem
		prim();

		// Output
		cout << "Case #" << tc << endl << result << endl;
	}

	return 0;
 }