Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
0
Indexable
Never
package bla;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static boolean [] vis = new boolean[1000];
	static int [] key = new int[1000];
	static int [] parent = new int[1000];
	static int n;
	public static int findMin(){
		int ret = 0;
		int min = 10000;
		for (int i = 0; i < n; i++) {
			if(vis[i]==false && key[i] < min){
				min = key[i];
				ret = i;
			}
		}
		return ret;
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			n = sc.nextInt();
			int result = 0;
			int arr[][] = new int [n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			for (int i = 0; i < n; i++) {
				vis[i] = false;
				key[i] = 10000;
				parent[i] = -1;
			}
			key[0]= 0;
			for (int i = 0; i < n-1; i++) {
				int u = findMin();
				vis[u] = true;
				for (int j = 0; j < n; j++) {
					if(vis[j]==false && arr[u][j] < key[j]){
						key[j] = arr[u][j];
						parent[j] = u;
					}
				}
			}
			for (int i = 0; i < n; i++) {
				result += key[i];
			}
			System.out.println("Case #"+tc);
			System.out.println(result);
		}
	}
}