(UVA) Hotel Booking - Solution

In order to solve this problem, I used Dijkstra's algorithm.

Every time I arrive in a city, and this city has a hotel, I will try to continue without using this hotel. I will also add the possibility of using the hotel in my queue. This PriorityQueue is sorted based on the quantity of hotels and, if there is a tie, it is sorted based on the amount of minutes the driver is driving.

Furthermore, I may visit again a city that was previously visited if I used a new hotel since the last visit. 


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

class Main  {
    public static HashSet<Integer> locHotels;
    public static HashMap<Integer, ArrayList<Edge>> adjList;
  
    public static Comparator<Travel> timeComparator = new Comparator<Travel>() {
        public int compare(Travel t1, Travel t2) {
            if ((t1.qtyHotels - t2.qtyHotels) < 0) {
                return -1;
            }
            else if ((t1.qtyHotels - t2.qtyHotels) > 0) {
                return 1;
            }
            else {
                return t1.minutes - t2.minutes;
            }
        }
    };
  
    public static int dijkstra(int start, int end, int numCities, int hotels) {
        Queue<Travel> queue = new PriorityQueue<Travel>(numCities, timeComparator);
        Travel t = new Travel(new Edge(start, 0), 0, 0);
        queue.add(t);
       
        boolean[][] visited = new boolean[numCities+1][hotels+1];
           
        while (queue.size() > 0) {
            Travel currEdge = queue.poll();
            int currCity = currEdge.e.city;
            int currCost = currEdge.e.cost;
            int currMinutes = currEdge.minutes;
            int numHotels = currEdge.qtyHotels;
            boolean hasHotel = locHotels.contains(currCity);

            if (numHotels > hotels) {
                continue;
            }
           
            if (currMinutes > 600) {
                continue;
            }
           
            if (currCity == end) {
                return numHotels;
            }
           
            if (visited[currCity][numHotels]) {
                continue;
            }
          
            visited[currCity][numHotels] = true;

            if (hasHotel) {
                t = new Travel(new Edge(currCity, currCost), 0, numHotels+1);
                queue.add(t);
            }

            ArrayList<Edge> reachCities = adjList.get(currCity);
            for (int i = 0; i < reachCities.size(); i++) {
                Edge next = reachCities.get(i);
              
                t = new Travel(new Edge(next.city, currCost+next.cost), currMinutes+next.cost, numHotels);
                queue.add(t);      
            }
        }
      
        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);
        while (numCities != 0) {
            int numHotels = reader(br);
            locHotels = new HashSet<Integer>();
            for (int i = 0; i < numHotels; i++) {
                locHotels.add(reader(br));
            }

            adjList = new HashMap<Integer, ArrayList<Edge>>();
            for (int i = 0; i < numCities; i++) {
                adjList.put((i+1), new ArrayList<Edge>());
            }
          
            int numPaths = reader(br);
            for (int i = 0; i < numPaths; i++) {
                int c1 = reader(br);
                int c2 = reader(br);
                int cost = reader(br);
              
                Edge e = new Edge(c2, cost);
                adjList.get(c1).add(e);
              
                e = new Edge(c1, cost);
                adjList.get(c2).add(e);
            }
          
            int numNecHotels = dijkstra(1, numCities, numCities, numHotels);
            System.out.println(numNecHotels);
          
            numCities = 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;
    }
}

class Travel {
    Edge e;
    int minutes;
    int qtyHotels;
  
    public Travel(Edge e, int m, int qH) {
        this.e = e;
        minutes = m;
        qtyHotels = qH;
    }
}