Untitled
unknown
plain_text
25 days ago
1.7 kB
1
Indexable
Never
import java.util.Scanner; class MinimumPipelineLength { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int caseNumber = 1; caseNumber <= t; caseNumber++) { int n = scanner.nextInt(); int[][] distance = new int[n][n]; boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { distance[i][j] = scanner.nextInt(); } } int minPipelineLength = prim(distance, visited); System.out.println("Case #" + caseNumber); System.out.println(minPipelineLength); } } static int prim(int[][] distance, boolean[] visited) { int n = distance.length; int[] minDistance = new int[n]; for (int i = 0; i < n; i++) { minDistance[i] = Integer.MAX_VALUE; } minDistance[0] = 0; int result = 0; for (int i = 0; i < n; i++) { int u = -1; for (int j = 0; j < n; j++) { if (!visited[j] && (u == -1 || minDistance[j] < minDistance[u])) { u = j; } } visited[u] = true; result += minDistance[u]; for (int v = 0; v < n; v++) { if (!visited[v] && distance[u][v] < minDistance[v]) { minDistance[v] = distance[u][v]; } } } return result; } }