(UVA) Lift Hopping - Solution 2

I used Dijkstra's algorithm to solve this problem.

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

The difference between this solution and the previous one is that in the first solution, I used only one structure that maps each floor to an array of floors & cost. Therefore, I did not have a different structure for each elevator. Then, it was necessary to apply some calculus to get the floor of a specific elevator.

In the second solution, I use one structure that contains the elevator, an array of floors for each elevator, and an array of floors & cost for each one of the floors. Then, it is not necessary to apply any additional calculus to get a floor. Therefore, it reduces the time of execution. 


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

class Main  {
    public static int[] speedElevators;
    public static ArrayList<ArrayList<ArrayList<Edge>>> graph;
   
    public static Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost-e2.cost;
        }
    };
   
    public static int dijkstra(int start, int dest, int numElevators) {
        Queue<Edge> queue = new PriorityQueue<Edge>(100, costComparator);
        for (int i = 0; i < numElevators; i++) {
            queue.add(new Edge(i, start, 0));
        }
       
        boolean[][] visited = new boolean[numElevators][100];
       
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currElevator = curr.elevator;
            int currFloor = curr.floor;
            int currCost = curr.cost;
           
            if (visited[currElevator][currFloor]) {
                continue;
            }
            visited[currElevator][currFloor] = true;
           
            if (currFloor == dest) {
                return currCost;
            }
           
            ArrayList<Edge> reachFloors = graph.get(currElevator).get(currFloor);
            for (int i = 0; i < reachFloors.size(); i++) {
                queue.add(new Edge(reachFloors.get(i).elevator, reachFloors.get(i).floor, reachFloors.get(i).cost+currCost));
            }
        }
       
        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));
       
        String line = br.readLine();
        while (line != null) {
            String[] s = line.split("\\s");
            int numElevators = Integer.parseInt(s[0]);
            int floorDest = Integer.parseInt(s[1]);
           
            speedElevators = new int[numElevators];
            for (int i = 0; i < numElevators; i++) {
                speedElevators[i] = reader(br);
            }
           
            graph = new ArrayList<ArrayList<ArrayList<Edge>>>();
            for (int i = 0; i < numElevators; i++) {
                graph.add(new ArrayList<ArrayList<Edge>>());
                for (int j = 0; j < 100; j++) {
                    graph.get(i).add(new ArrayList<Edge>());
                }
            }
           
            for (int i = 0; i < numElevators; i++) {
                line = br.readLine();
                s = line.split("\\s");
                int previousFloor = 0;
                if (s.length > 0) {
                    previousFloor = Integer.parseInt(s[0]);
                }
                for (int j = 1; j < s.length; j++) {
                    int currFloor = Integer.parseInt(s[j]);
                    graph.get(i).get(previousFloor).add(new Edge(i, currFloor, (currFloor-previousFloor)*speedElevators[i]));
                    graph.get(i).get(currFloor).add(new Edge(i, previousFloor, (currFloor-previousFloor)*speedElevators[i]));
                   
                    previousFloor = currFloor;
                }
            }
           
            for (int i = 0; i < 100; i++) {
                for (int j = 0; j < numElevators; j++) {
                    for (int k = j+1; k < numElevators; k++) {
                        if (graph.get(j).get(i).size() != 0 && graph.get(k).get(i).size() != 0) {
                            graph.get(j).get(i).add(new Edge(k, i, 60));
                            graph.get(k).get(i).add(new Edge(j, i, 60));
                        }
                    }
                }
            }
                
            int totalCost = dijkstra(0, floorDest, numElevators);
            if (totalCost == -1) {
                System.out.println("IMPOSSIBLE");
            }
            else {
                System.out.println(totalCost);
            }
           
            line = br.readLine();
        }
               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Edge {
    int elevator;
    int floor;
    int cost;
   
    public Edge(int e, int f, int c) {
        elevator = e;
        floor = f;
        cost = c;
    }
}