(SPOJ) Reunião - Solution 2

Link to the problem: http://br.spoj.com/problems/REUNIAO2/

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

The solution below calls the Dijkstra method for every city where the reunion could be taken. Then, it is possible to know what is going to be the maximum distance that a driver will have to drive if a specific city was chosen. Finally, we only need to find the minimum distance among these maximum distances, and we will have our answer for the problem.


import java.io.*;
import java.util.*;

class Main {
    public HashMap<Integer, ArrayList<Edge>> adjList;
   
    public Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost-e2.cost;
        }
    };
   
    public int dijkstra(int end, int numCities) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numCities, costComparator);
        queue.add(new Edge(end, 0));
       
        HashSet<Integer> visited = new HashSet<>();
       
        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 (visited.size() == numCities) {
                return currCost;
            }
           
            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+currCost));
            }
        }
       
        return -1;
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        String[] s = line.split("\\s");
        int numCities = Integer.parseInt(s[0]);
        int numRoads = Integer.parseInt(s[1]);
           
        adjList = new HashMap<>();           
        for (int i = 0; i < numCities; i++) {
            adjList.put(i, new ArrayList<Edge>());
        }
       
        for (int i = 0; i < numRoads; i++) {
            line = br.readLine();
            s = line.split("\\s");
            int c1 = Integer.parseInt(s[0]);
            int c2 = Integer.parseInt(s[1]);
            int cost = Integer.parseInt(s[2]);
           
            adjList.get(c1).add(new Edge(c2, cost));
            adjList.get(c2).add(new Edge(c1, cost));
        }
       
        int minDistance = 2000000000;
        for (int end = 0; end < numCities; end++) {
            int maxDistance = dijkstra(end, numCities);
            minDistance = Math.min(minDistance, maxDistance);
        }
       
        System.out.println(minDistance);
                          
        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;
    }
}