(UVA) Lift Hopping - Solution 1

I used Dijkstra's algorithm to solve this problem.


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

class Main  {
    public static int[] speedElevators;
    public static HashMap<Integer, 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*100, 0));
        }
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currFloor = curr.floor;
            int currCost = curr.cost;
           
            if (visited.contains(currFloor)) {
                continue;
            }
            visited.add(currFloor);
           
            if (currFloor%100 == dest) {
                return currCost;
            }
           
            ArrayList<Edge> reachFloors = graph.get(currFloor);
            for (int i = 0; i < reachFloors.size(); i++) {
                queue.add(new Edge(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 HashMap<Integer, ArrayList<Edge>>();
            for (int i = 0; i < (100*numElevators); i++) {
                graph.put(i, 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*100+previousFloor).add(new Edge(i*100+currFloor, (currFloor-previousFloor)*speedElevators[i]));
                    graph.get(i*100+currFloor).add(new Edge(i*100+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*100)+i) != null && graph.get((k*100)+i) != null) {
                            graph.get((j*100)+i).add(new Edge((k*100)+i, 60));
                            graph.get((k*100)+i).add(new Edge((j*100)+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 floor;
    int cost;
   
    public Edge(int f, int c) {
        floor = f;
        cost = c;
    }
}