Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
16
Indexable
Never
#include <iostream>
#define INF 99999

using namespace std;

int adj[100][100];
int visit[100], key[100], parent[100];
int N;

void input()
{
	cin >> N;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> adj[i][j];
		}
	}
}

void reset()
{
	for(int i = 0; i < N; i++){
		visit[i] = 0;
		key[i] = INF;
		parent[i] = -1;
	}
}

int findMin()
{
	int ret;
	int min = INF;
	for(int v = 0; v < N; v++){
		if(visit[v] == 0 && key[v] < min){
			min = key[v];
			ret = v;
		}
	}
	return ret;
}

int main()
{
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		input();
		reset();
		key[0] = 0;
		//visit[0] = 1;
		for(int i = 0; i < N -1; i++){
			int u = findMin();
			visit[u] = 1;
			for(int v = 0; v < N; v++){
				if(visit[v] == 0 && adj[u][v] < key[v]){
					key[v] = adj[u][v];
					parent[v] = u;
				}
			}
		}
		int sum = 0;
		for(int i = 0; i<N; i++){
			sum += key[i];
		}
		cout << "Case #" << tc << endl;
		cout << sum << endl;
	}
	return 0;
}

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