(UVA) Driving Range - 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.*;

class Main {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
   
    public static Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost-e2.cost;
        }
    };
   
    public static int prim(int start, int numCities) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numCities, costComparator);
        queue.add(new Edge(start, 0));
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        int maxCost = -1;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currCity = curr.city;
            int currCost = curr.cost;
           
            if (visited.contains(currCity)) {
                continue;
            }
            visited.add(currCity);
           
            if (currCost > maxCost) {
                maxCost = currCost;
            }
           
            if (visited.size() == numCities) {
                return maxCost;
            }
           
            ArrayList<Edge> reachCities = adjList.get(currCity);
            for (int i = 0; i < reachCities.size(); i++) {
                queue.add(new Edge(reachCities.get(i).city, reachCities.get(i).cost));
            }
        }
       
        return -1;
    }
   
    public static int reader (BufferedReader br) throws NumberFormatException, IOException {
        int n;
        int resp = 0;
        
        while (true) {
            n = br.read();
            if (n >= '0' && n <= '9') break;
        }
        while (true) {
            resp = resp*10 + n-'0';
            n = br.read();
            if (n < '0' || n > '9') break;
        }
        
        return resp;
    }
   
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCities = reader(br);
        int numRoads = reader(br);
        while (numCities != 0 || numRoads != 0) {
            adjList = new HashMap<Integer, ArrayList<Edge>>();
            for (int i = 0; i < numCities; i++) {
                adjList.put(i, new ArrayList<Edge>());
            }
           
            for (int i = 0; i < numRoads; i++) {
                int c1 = reader(br);
                int c2 = reader(br);
                int cost = reader(br);
               
                adjList.get(c1).add(new Edge(c2, cost));
                adjList.get(c2).add(new Edge(c1, cost));
            }
           
            int maxCost = prim(0, numCities);
           
            if (maxCost != -1) {
                System.out.println(maxCost);
            }
            else {
                System.out.println("IMPOSSIBLE");
            }
           
            numCities = reader(br);
            numRoads = reader(br);
        }
                                             
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Edge {
    int city;
    int cost;
   
    public Edge(int city, int cost) {
        this.city = city;
        this.cost = cost;
    }
}