(UVA) Non-Stop Travel - Solution

I used Dijkstra's algorithm to solve this problem.


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

class Main  {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
    public static String pathNodes;
   
    public static Comparator<Path> costComparator = new Comparator<Path>() {
        public int compare(Path p1, Path p2) {
            return p1.e.cost-p2.e.cost;
        }
    };
   
    public static int dijkstra(int start, int end) {
        Queue<Path> queue = new PriorityQueue<Path>(10, costComparator);
        Path p = new Path(new Edge(start, 0), "");
        queue.add(p);

        HashSet<Integer> visited = new HashSet<Integer>();
       
        while (queue.size() > 0) {
            Path curr = queue.poll();
            int currNode = curr.e.node;
            int currCost = curr.e.cost;
            StringBuilder currPath = new StringBuilder(curr.path);
           
            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);
           
            currPath.append(currNode + " ");
            if (currNode == end) {
                pathNodes = currPath.toString();
                return currCost;
            }
           
            ArrayList<Edge> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                Edge e = reachNodes.get(i);
                queue.add(new Path(new Edge(e.node, e.cost+currCost), currPath.toString()));
            }
        }
       
        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 numCase = 0;
        int numIntersections = reader(br);
        while (numIntersections != 0) {
            adjList = new HashMap<Integer, ArrayList<Edge>>();
            for (int i = 1; i <= numIntersections; i++) {
                adjList.put(i, new ArrayList<Edge>());
            }
           
            for (int i = 0; i < numIntersections; i++) {
                int numStreets = reader(br);
                for (int j = 0; j < numStreets; j++) {
                    int to = reader(br);
                    int cost = reader(br);
                    Edge e = new Edge(to, cost);
                    adjList.get(i+1).add(e);
                }
            }
           
            int start = reader(br);
            int end = reader(br);
            int delay = dijkstra(start, end);
            System.out.print("Case " + ++numCase + ": Path = " + pathNodes.substring(0, pathNodes.length()-1) + "; " + delay + " second delay\n");
           
            numIntersections = reader(br);
        }
                                               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Edge {
    int node;
    int cost;
   
    public Edge(int n, int c) {
        node = n;
        cost = c;
    }
}

class Path {
    Edge e;
    String path;
   
    public Path(Edge e, String path) {
        this.e = e;
        this.path = path;
    }
}