fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4.  
  5. public class Main {
  6.    static int numDots;
  7.    static Node[] adjacencyList;
  8.  
  9.    static class Node{
  10.       double key;
  11.       boolean visited;
  12.       int data;
  13.       double x;
  14.       double y;
  15.       ArrayList<Node> children;
  16.       Node parent;
  17.       public Node(double x, double y, int data){
  18.          this.data = data;
  19.          this.x = x;
  20.          this.y = y;
  21.          visited = false;
  22.          key = Double.MAX_VALUE;
  23.          children = new ArrayList<Node>();
  24.          parent = null;
  25.       }
  26.  
  27.    }
  28.  
  29.    public static void main(String[] args) {
  30.       Scanner sc = new Scanner(System.in);
  31.       int numCases = sc.nextInt();
  32.       sc.nextLine();
  33.       for(int g = 0; g<numCases; g++){
  34.          sc.nextLine();
  35.          numDots = sc.nextInt();
  36.          adjacencyList = new Node[numDots];
  37.          for(int a = 0; a<numDots; a++){
  38.             Node n = new Node(sc.nextDouble(), sc.nextDouble(), a);
  39.             adjacencyList[a] = n;
  40.          }
  41.  
  42.          //add children to each node
  43.          for(int b = 0; b<numDots; b++){
  44.             for(int c = 0; c<numDots; c++){
  45.                if(b!=c)
  46.                   adjacencyList[b].children.add(adjacencyList[c]);
  47.             }
  48.          }
  49.  
  50.          adjacencyList[0].key = 0;
  51.  
  52.          for(int a = 0; a<numDots; a++){
  53.             int u = getMinKey();
  54.             adjacencyList[u].visited = true;
  55.             for(int b = 0; b<numDots; b++){
  56.                double newKey = 0;
  57.                if(adjacencyList[b].visited == false && (newKey = Math.sqrt(Math.pow(Math.abs(adjacencyList[u].x-adjacencyList[b].x), 2.0) +
  58.                      Math.pow(Math.abs(adjacencyList[u].y - adjacencyList[b].y), 2.0)))  < adjacencyList[b].key){
  59.                   adjacencyList[b].key = newKey;
  60.                   adjacencyList[b].parent = adjacencyList[u];
  61.  
  62.                }
  63.             }
  64.          }
  65.  
  66.          double sum = 0;
  67.          for(int z = 0; z<numDots; z++){
  68.             sum+=adjacencyList[z].key;
  69.          }
  70.          System.out.printf("%.2f",sum);
  71.          if(g<numCases-2)
  72.          System.out.println("\n");
  73.  
  74.       }
  75.    }
  76.    public static int getMinKey(){
  77.       int minIndex = 0;
  78.  
  79.       double minKey = Double.MAX_VALUE;
  80.       for(int a = 0; a<numDots; a++){
  81.          if(adjacencyList[a].visited == false && adjacencyList[a].key < minKey){
  82.             minKey = adjacencyList[a].key;
  83.             minIndex = a;
  84.          }
  85.       }
  86.  
  87.       return minIndex;
  88.    }
  89. }
  90.  
Success #stdin #stdout 0.13s 380672KB
comments (?)
stdin
copy 
2

3
1.0 1.0
2.0 2.0
2.0 4.0

3
1.0 1.0
2.0 2.0
2.0 4.0
stdout
copy 
3.413.41
https://ideone.com/mXzi7e
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!