//{ Driver Code Starts import java.util.*; import java.io.*; import java.lang.*; public class Main{ static BufferedReader br; static PrintWriter ot; public static void main(String args[]) throws IOException { br = new BufferedReader(new InputStreamReader(System.in)); ot = new PrintWriter(System.out); int t = Integer.parseInt(br.readLine().trim()); while(t-- > 0){ String s[] = br.readLine().trim().split(" "); int V = Integer.parseInt(s[0]); int E = Integer.parseInt(s[1]); int edges[][] = new int[E][3]; for(int i = 0; i < E; i++){ s = br.readLine().trim().split(" "); edges[i][0] = Integer.parseInt(s[0]); edges[i][1] = Integer.parseInt(s[1]); edges[i][2] = Integer.parseInt(s[2]); } ot.println(new Solution().spanningTree(V, E, edges)); } ot.close(); } } // } Driver Code Ends // User function Template for Java class Solution{ static int spanningTree(int V, int E, int edges[][]){ ArrayList<ArrayList<pair>> graph = new ArrayList<>(); for(int i = 0 ;i < V ; i++) graph.add(new ArrayList<>()); for(int[] edge : edges){ graph.get(edge[0]).add(new pair(edge[1],edge[2])); graph.get(edge[1]).add(new pair(edge[0],edge[2])); } PriorityQueue<pair> q = new PriorityQueue<>(); q.add(new pair(0 , 0)); int ans = 0; boolean visited[] = new boolean[V]; while(q.size() > 0){ pair rem = q.poll(); int v = rem.v ,wt = rem.wt; if(visited[v] == true) continue; visited[v] = true; // System.out.print(v + " " + wt + "\n"); ans += wt; for(pair edge : graph.get(v)){ if(visited[edge.v] == false){ q.add(new pair(edge.v , edge.wt)); } } } return ans; } public static class pair implements Comparable<pair>{ int v , wt ; pair(int v , int wt){ this. v = v; this.wt = wt; } public int compareTo(pair o){ return this.wt - o.wt; } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter