(UVA) Transportation System - Solution 2

If you want to see another solution for this problem, click here.

I used Prim's algorithm to solve this problem.


import java.io.*;
import java.util.*;
import java.lang.Math;

class Main {
    public static Coord[] cities;
    public static int numStates;
    public static double lengthRoads;
    public static double lengthRailroads;
   
    public static Comparator<Edge> lengthComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            if (e1.length-e2.length < 0) {
                return -1;
            }
            else if (e1.length-e2.length > 0) {
                return 1;
            }
           
            return 0;
        }
    };
   
    public static void prim(int start, int numCities, int maxLength) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numCities, lengthComparator);
        Edge e = new Edge(start, 0.0);
        queue.add(e);
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currNode = curr.node;
            double currLength = curr.length;

            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);

           
            if (currLength > maxLength) {
                numStates++;
                lengthRailroads += currLength;
            }
            else {
                lengthRoads += currLength;
            }
           
            if (visited.size() == numCities) {
                return;
            }

            for (int i = 0; i < numCities; i++) {
                if (i == currNode) {
                    continue;
                }
                double d = dist(cities[currNode], cities[i]);
                queue.add(new Edge(i, Math.sqrt(d)));
            }           
        }
    }
       
    public static double dist(Coord c1, Coord c2) {
        return (c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y);
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numCases = sc.nextInt();
        for (int i = 0; i < numCases; i++) {
            int numCities = sc.nextInt();
            int lengthTwoCities = sc.nextInt();
            cities = new Coord[numCities];
            for (int j = 0; j < numCities; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                cities[j] = new Coord(x, y);
            }
           
            numStates = 1;
            lengthRoads = 0.0;
            lengthRailroads = 0.0;
            prim(0, numCities, lengthTwoCities);
           
            System.out.println("Case #" + (i+1) + ": " + numStates + " " + Math.round(lengthRoads) + " " + Math.round(lengthRailroads));
        }
                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Coord {
    int x;
    int y;
   
    public Coord(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Edge {
    int node;
    double length;
   
    public Edge(int node, double length) {
        this.node = node;
        this.length = length;
    }
}