Untitled

mail@pastecode.io avatar
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;
    }
}