fork download
copy 
  1. import java.util.Scanner;
  2. import java.util.ArrayList;
  3. import java.util.Comparator;
  4. import java.util.HashMap;
  5. import java.util.Iterator;
  6. import java.util.LinkedList;
  7. import java.util.Map;
  8. import java.util.PriorityQueue;
  9.  
  10. public class Main {
  11.  
  12.     public static void main(String[] args) {
  13.          try{
  14.             Scanner sc=new Scanner(System.in);
  15.             int n=sc.nextInt();
  16.             int m=sc.nextInt();
  17.             graph g=new graph();
  18.             for (int i = 0; i < n; i++) {
  19.                  g.addVertex(new vertex(i+1));
  20.              }
  21.            for (int i = 0; i < m; i++) {
  22.                  vertex src=g.vertexList.get(sc.nextInt()-1);
  23.                  vertex dest=g.vertexList.get(sc.nextInt()-1);
  24.                  int weight=sc.nextInt();
  25.                  g.addEdge(src, dest, weight);
  26.              }
  27.              System.out.println(g.primAlgo());
  28.          }
  29.         catch(Exception e){
  30. //            System.out.println("error occured");
  31.         }
  32.     }
  33.  
  34. }
  35. class graph // it is a directed and weighted graph
  36. {
  37.  
  38.  
  39.     public ArrayList<vertex> vertexList;
  40.  
  41.     public int numOfVertices;
  42.     public ArrayList<vertex> artPoints;
  43.  
  44.     public ArrayList<LinkedList<edge>> adjList;
  45.  
  46.     public graph() {
  47.  
  48.  
  49.         vertexList = new ArrayList<>();
  50.  
  51.         adjList = new ArrayList<>();
  52.         artPoints=new ArrayList<>();
  53.  
  54.         numOfVertices = 0;
  55.  
  56.     }
  57.  
  58.     public void addVertex(vertex vert) {
  59.  
  60.         vertexList.add(vert);
  61.  
  62.         adjList.add(new LinkedList<>());
  63.  
  64.         numOfVertices++;
  65.  
  66.     }
  67.  
  68.    public void addEdge(vertex source, vertex destination, int weight) {
  69.  
  70.                 edge lp = new edge(source, destination,weight);
  71.                 adjList.get(source.label-1).add(lp);
  72.                 lp = new edge(destination, source, weight);
  73.                 adjList.get(destination.label-1).add(lp);
  74.         }
  75.  
  76. //      public vertex getAdjacent(vertex vert) {
  77. //          LinkedList<edge> p = adjList.get(vert.label-1);
  78. // //         System.out.println("inside getAdjacent function which has neighbours "+p.size());
  79. //          Iterator it = p.iterator();
  80. //          while (it.hasNext()) {
  81. //              edge j = (edge) it.next();
  82. //              if (!j.destination.visited) {
  83. //                  j.destination.visited = true;
  84. // //                 System.out.println("returning neighbour "+j.destination.label);
  85. //                  return j.destination;
  86. //              }
  87. //          }
  88. //          return null;
  89. //     }
  90.      public long primAlgo(){
  91.          Map<vertex,Boolean> mp=new  HashMap<>();
  92.          PriorityQueue<vertex> pq=new PriorityQueue<>(new Comparator<vertex>(){
  93.              @Override
  94.              public int compare(vertex t, vertex t1) {
  95.         	  if(t.value<t1.value)   
  96.                   return -1;
  97.       		else if(t.value==t1.value)   
  98.                   return 0;
  99.               else
  100.                   return 1;
  101.              } 
  102.          });
  103.          vertexList.get(0).value=0;
  104.          for (int i = 0; i < vertexList.size(); i++) {
  105.              pq.offer(vertexList.get(i));
  106.          }
  107.          while(mp.size()!=vertexList.size()){
  108.          	 PriorityQueue<vertex> temp=new PriorityQueue<>(new Comparator<vertex>(){
  109.              @Override
  110.              public int compare(vertex t, vertex t1) {
  111.                if(t.value<t1.value)   
  112.                   return -1;
  113.       		else if(t.value==t1.value)   
  114.                   return 0;
  115.               else
  116.                   return 1;
  117.              } 
  118.          });
  119.          while(!pq.isEmpty())
  120.          	temp.offer(pq.poll());
  121.      	 while(!temp.isEmpty())
  122.          	pq.offer(temp.poll());
  123.              vertex v=pq.peek();
  124.              v.visited=true;
  125. //             System.out.println("considering vertex "+v.label);
  126.              if(mp.containsKey(v))
  127.              {
  128.                  pq.poll();
  129. //                 System.out.println("popping it");
  130.              }
  131.              else{
  132.                  mp.put(v,true);
  133.                  if(v!=vertexList.get(0))
  134.                  {
  135.                      if(v.value==Integer.MAX_VALUE)
  136.                          v.value=0;
  137.                  }
  138.                  LinkedList<edge> lt=adjList.get(v.label-1);
  139.                  for (edge e: lt) {
  140.                      if(!e.destination.visited)
  141.                      {
  142. //                         System.out.println("old value of  "+e.destination.label+" is "+e.destination.value);
  143.                          int min=Math.min(e.destination.value,e.weight);
  144.                         if(min<e.destination.value)
  145.                         {
  146.                             e.destination.value=min;
  147.                             // pq.offer(e.destination);
  148.                         }
  149. //                        System.out.println("new value is "+e.destination.value);
  150.                      }
  151.                  }
  152.              }
  153.          }
  154.          long sum=0;
  155.          for (int i = 0; i < vertexList.size(); i++) {
  156.              sum+=vertexList.get(i).value;
  157. //             System.out.println("updated sum is "+sum);
  158.          }
  159.          return sum;
  160.      }
  161.  
  162. }
  163.  
  164. class vertex {
  165.  
  166.     public int label;
  167.     public int value;
  168.     public boolean visited;
  169.  
  170.     public vertex(int label) {
  171.  
  172.         this.label = label;
  173.         this.value=Integer.MAX_VALUE;
  174.         this.visited=false;
  175.     }
  176.  
  177. }
  178.  
  179. class edge {
  180.  
  181.     vertex source, destination;
  182.  
  183.     int weight;
  184.  
  185.     public edge(vertex source, vertex destination, int weight) {
  186.  
  187.         this.source = source;
  188.  
  189.         this.destination = destination;
  190.  
  191.         this.weight = weight;
  192.  
  193.     }
  194. }
Success #stdin #stdout 0.08s 2184192KB
comments (?)
stdin
copy 
4 5
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40
stdout
copy 
17
https://ideone.com/2xreyb
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!