(UVA) Almost Shortest Path - Solution 2

I used Dijkstra's algorithm to solve this problem.

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

In both solutions I used two Dijkstras.

The difference between this solution and the previous one is that here I keep only the parent of each point in my queue. For every point, I keep a list of parents because if it is possible to reach a point through more than one point with the same shortest cost, I have to add all these points to my list.

In the end of the first Dijkstra, I call another method responsible for iterate over the list of parents to remove the edges that belong to the shortest path from the start to the end point.

Finally, I call the second Dijkstra, which will give the answer.


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

class Main  {
    public static HashMap<Integer, ArrayList<SimpleEdge>> adjList;
    public static ArrayList<ArrayList<Integer>> parents;
    public static int[] costs;
  
    public static Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost-e2.cost;
        }
    };
  
    public static void removeEdges(int end) {
        Queue<Integer> curr = new ArrayDeque<Integer>();
        curr.add(end);
      
        HashSet<Integer> visited = new HashSet<Integer>();
        while (curr.size() > 0) {
            int currPoint = curr.poll();
            visited.add(currPoint);
            ArrayList<Integer> list = parents.get(currPoint);
            for (int i = 0; i < list.size(); i++) {
                int point = list.get(i);
                if (!visited.contains(point)) {
                    curr.add(point);
                }
                ArrayList<SimpleEdge> list2 = adjList.get(point);
                for (int j = 0; j < list2.size(); j++) {
                    if (list2.get(j).point == currPoint) {
                        list2.remove(j);
                    }
                }
            }
        }
    }
  
    public static int dijkstra2(int start, int end, int numPoints) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numPoints, costComparator);
        queue.add(new Edge(start, 0, start));
      
        HashSet<Integer> visited = new HashSet<Integer>();
      
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currPoint = curr.point;
            int currCost = curr.cost;
            int currParent = curr.parent;
          
            if (visited.contains(currPoint)) {
                continue;
            }
            visited.add(currPoint);
          
            if (currPoint == end) {
                return currCost;
            }
          
            ArrayList<SimpleEdge> reachPoints = adjList.get(currPoint);
            for (int i = 0; i < reachPoints.size(); i++) {
                queue.add(new Edge(reachPoints.get(i).point, reachPoints.get(i).cost+currCost, currPoint));
            } 
        }
      
        return -1;
    }
  
    public static void dijkstra(int start, int end, int numPoints) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numPoints, costComparator);
        queue.add(new Edge(start, 0, start));
      
        HashSet<Integer> visited = new HashSet<Integer>();
      
        boolean firstAnswer = true;
        int shortestPathCost = 0;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currPoint = curr.point;
            int currCost = curr.cost;
            int currParent = curr.parent;

            if (currPoint != start && costs[currPoint] > currCost) {
                costs[currPoint] = currCost;
                for (int i = 0; i < parents.get(currPoint).size(); i++) {
                    parents.get(currPoint).remove(i);
                }
                parents.get(currPoint).add(currParent);
            }
            else if (currPoint != start && costs[currPoint] == currCost) {
                parents.get(currPoint).add(currParent);
            }
          
            if (visited.contains(currPoint)) {
                continue;
            }
            visited.add(currPoint);
          
            ArrayList<SimpleEdge> reachPoints = adjList.get(currPoint);
            for (int i = 0; i < reachPoints.size(); i++) {
                queue.add(new Edge(reachPoints.get(i).point, reachPoints.get(i).cost+currCost, currPoint));
            } 
        }

        removeEdges(end);
        return;
    }
  
    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 numPoints = reader(br);
        int numRoutes = reader(br);
        while (numPoints != 0 || numRoutes != 0) {
            int start = reader(br);
            int end = reader(br);
          
            adjList = new HashMap<Integer, ArrayList<SimpleEdge>>();
            for (int i = 0; i < numPoints; i++) {
                adjList.put(i, new ArrayList<SimpleEdge>());
            }
          
            for (int i = 0; i < numRoutes; i++) {
                int p1 = reader(br);
                int p2 = reader(br);
                int cost = reader(br);
          
                adjList.get(p1).add(new SimpleEdge(p2, cost));
            }
          
            parents = new ArrayList<ArrayList<Integer>>();
            for (int i = 0; i < numPoints; i++) {
                parents.add(new ArrayList<Integer>());
            }
            costs = new int[numPoints];
            for (int i = 0; i < numPoints; i++) {
                costs[i] = 2000000000;
            }
          
            dijkstra(start, end, numPoints);
          
            System.out.println(dijkstra2(start, end, numPoints));
          
            numPoints = reader(br);
            numRoutes = reader(br);
        }
              
        return;
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class SimpleEdge {
    int point;
    int cost;
  
    public SimpleEdge(int point, int cost) {
        this.point = point;
        this.cost = cost;
    }
}

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