(UVA) Mice and Maze - Solution 2

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

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

This solution is different from the previous one because I did not reverse the edges. Then, I call the Dijkstra's method once for each cell, which makes this solution worse. In this method, if the mouse reaches the exit cell in at most count-down time, this mouse exited the maze.


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

class Main  {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
   
    public static Comparator<Edge> timeComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost - e2.cost;
        }
    };
   
    public static int dijkstra(int start, int exitCell, int numCells, int countdownTimer) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numCells, timeComparator);
        Edge e = new Edge(start, 0);
        queue.add(e);
       
        HashSet<Integer> visited = new HashSet<Integer>();
        HashSet<Integer> cells = new HashSet<Integer>();
       
        while (queue.size() > 0) {
            Edge currEdge = queue.poll();
            int currCell = currEdge.cell;
            int currCost = currEdge.cost;
           
            if (visited.contains(currCell)) {
                continue;
            }
           
            visited.add(currCell);
           
            if (currCost > countdownTimer) {
                continue;
            }
           
            if (currCell == exitCell) {
                return 1;
            }
           
            ArrayList<Edge> reachCells = adjList.get(currCell);
            for (int i = 0; i < reachCells.size(); i++) {
                Edge next = reachCells.get(i);
                e = new Edge(next.cell, currCost+next.cost);
                queue.add(e);
            }
        }
       
        return 0;
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {    
        int n;
        int resp = 0;     
        int sinal = 1;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
            if (n == '-') {
                sinal = -1;
            }         
            if (n == '+') {
                sinal = 1;
            }    
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp*sinal;     
    }
      
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
        int numCases = reader(br);
        for (int i = 0; i < numCases; i++) {
            int numCells = reader(br);
            int exitCell = reader(br);
            int countdownTimer = reader(br);
           
            adjList = new HashMap<Integer, ArrayList<Edge>>();
            for (int j = 1; j <= numCells; j++) {
                adjList.put(j, new ArrayList<Edge>());
            }
           
            int numConnections = reader(br);
            for (int j = 0; j < numConnections; j++) {
                int a = reader(br);
                int b = reader(br);
                int cost = reader(br);
               
                Edge e = new Edge(b, cost);
                adjList.get(a).add(e);
            }
           
            int countMice = 0;
            for (int j = 1; j <= numCells; j++) {
                countMice += dijkstra(j, exitCell, numCells, countdownTimer);
            }
           
            if ((i+1) == numCases) {
                System.out.println(countMice);
            }
            else {
                System.out.println(countMice+"\n");
            }
        }
                        
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Edge {
    int cell;
    int cost;
   
    public Edge(int cell, int cost) {
        this.cell = cell;
        this.cost = cost;
    }
}