(URI) Países em Guerra - Solution

For this problem, I used Dijkstra's algorithm. Moreover, I also used a matrix and an adjacency list. The first one was necessary to keep the cost (hours) to send a message from a specific city to another one. The second structure was used to keep all the reachable cities in order to avoid iterating over an entire row of the matrix to acquire this information.


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

class Main  {
    public static HashMap<Integer, ArrayList<Element>> adjList;
    public static int[][] matrix;
  
    public static Comparator<Element> hoursComparator = new Comparator<Element>() {
        public int compare(Element e1, Element e2) {
            return (int) (e1.hours - e2.hours);
        }
    };
  
    public static int dijkstra(int cityStart, int cityEnd, int numCities) {
        Queue<Element> queue = new PriorityQueue<Element>(numCities, hoursComparator);
        Element e = new Element(cityStart, 0);
        queue.add(e);
      
        HashSet<Integer> visited = new HashSet<Integer>();
      
        while (queue.size() > 0) {
            Element currPos = queue.poll();
            int currCity = currPos.city;
            int currHours = currPos.hours;
            visited.add(currCity);
      
            if (currCity == cityEnd) {
                return currHours;
            }
          
            ArrayList<Element> reachableCities = adjList.get(currCity);
            for (int i = 0; i < reachableCities.size(); i++) {
                Element next = reachableCities.get(i);
                if (!visited.contains(next.city)) {
                    int hours = next.hours;
                    if (matrix[next.city][currCity] != -1) {
                        hours = 0;
                    }
                    e = new Element(next.city, currHours+hours);
                    queue.add(e);
                }
            }
        }
      
        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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int numCities = reader(br);
        int numPath = reader(br);
        while (numCities != 0 || numPath != 0) {
            matrix = new int[numCities+1][numCities+1];
            adjList = new HashMap<Integer, ArrayList<Element>>();
            for (int i = 1; i <= numCities; i++) {
                adjList.put(i, new ArrayList<Element>());
                for (int j = 1; j <= numCities; j++) {
                    matrix[i][j] = -1;
                }
            }
          
            for (int i = 0; i < numPath; i++) {
                int c1 = reader(br);
                int c2 = reader(br);
                int hours = reader(br);
                Element e = new Element(c2, hours);
                adjList.get(c1).add(e);
                matrix[c1][c2] = hours;
            }
          
            int queries = reader(br);
            for (int i = 0; i < queries; i++) {
                int c1 = reader(br);
                int c2 = reader(br);
                int hours = dijkstra(c1, c2, numCities);
                if (hours == -1) {
                    bw.write("Nao e possivel entregar a carta\n");
                }
                else {
                    bw.write(hours+"\n");
                }
            }
          
            bw.write("\n");
            numCities = reader(br);
            numPath = reader(br);
        }
                      
        bw.flush();
        bw.close();
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Element {
    int city;
    int hours;
  
    public Element(int c, int h) {
        city = c;
        hours = h;
    }
}