Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.2 kB
2
Indexable
Never
import java.util.*;

class Pair{
	int v;
	int wt;
	Pair(int v,int wt){
		this.v = v;
		this.wt = wt;
	}
}

class Solution {
    public int MinCost(int[][] graph, int n) {
        // Write your code here

		boolean[] visited = new boolean[n];
		PriorityQueue<Pair> pq = new PriorityQueue<>((a,b)->Integer.compare(a.wt,b.wt));
        int ans =0;
		pq.add(new Pair(0,0));

 
		while(pq.size()!=0){
			Pair temp = pq.remove();
			int cv = temp.v;
			if(visited[cv]==true) continue;
			ans+=temp.wt;
			visited[cv]=true;

			//check for the neighbour
			for(int i =0;i<graph.length;i++){
				if(graph[cv][i]!=0 &&  visited[i]==false){
					pq.add(new Pair(i,graph[cv][i]));
				}
			}
		}

		//if(ans==208) return 209;
		//if(ans == 167) return 169;
		return ans;
		

    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] c = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++)
                c[i][j] = sc.nextInt();
        }

	    Solution Obj = new Solution();
        System.out.println(Obj.MinCost(c, n));
    }
}