(UVA) Interstar Transport - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=3688

The problem asks us to find the sequence of direct transports that has the lowest travelling cost. For this reason, the solution below used Dijkstra.


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

class Main {
    public ArrayList<ArrayList<Edge>> adjList;
   
    public ArrayList<Integer> dijkstra(int start, int end) {
        Queue<Edge> queue = new PriorityQueue<>();
        queue.add(new Edge(start, 0, new ArrayList<Integer>()));
       
        HashSet<Integer> visited = new HashSet<>();
       
        int minCost = Integer.MAX_VALUE; // keep the minimum cost from start to end
        ArrayList<Integer> answer = new ArrayList<>(); // keep the nodes from start to end
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currPlanet = curr.planet;
            int currCost = curr.cost;
            ArrayList<Integer> currParent = (ArrayList<Integer>) curr.parent.clone();
           
            if (visited.contains(currPlanet)) {
                continue;
            }
            if (currPlanet != end) { // I need to visit end more than once
                visited.add(currPlanet);
            }
            currParent.add(currPlanet);

            if (currPlanet == end) {
                if (answer.size() == 0) { // reach the end for the first time
                    answer = (ArrayList<Integer>) currParent.clone();
                    minCost = currCost;
                }
                else if (currCost == minCost && currParent.size() < answer.size()) { // reach the end more than once (need to check if the path is equal to the minimum cost and how many nodes were visited)
                    answer = (ArrayList<Integer>) currParent.clone();
                }
            }
           
            ArrayList<Edge> reachPlanets = adjList.get(currPlanet);
            for (int i = 0; i < reachPlanets.size(); i++) {
                queue.add(new Edge(reachPlanets.get(i).planet, currCost+reachPlanets.get(i).cost, currParent));
            }
        }
       
        return answer;
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numPlanets = sc.nextInt();
        int numConnections = sc.nextInt();
       
        adjList = new ArrayList<>();
        for (int i = 0; i < 27; i++) {
            adjList.add(new ArrayList<Edge>());
        }
       
        for (int i = 0; i < numConnections; i++) {
            int p1 = sc.next().charAt(0)-'A';
            int p2 = sc.next().charAt(0)-'A';
            int cost = sc.nextInt();
           
            adjList.get(p1).add(new Edge(p2, cost, null));
            adjList.get(p2).add(new Edge(p1, cost, null));
        }
           
        int numQueries = sc.nextInt();
        for (int i = 0; i < numQueries; i++) {
            int start = sc.next().charAt(0)-'A';
            int end = sc.next().charAt(0)-'A';
            ArrayList<Integer> parentList = dijkstra(start, end);
            for (int j = 0; j < parentList.size(); j++) {
                if (j == parentList.size()-1) {
                    bw.write((char)(parentList.get(j)+'A')+"\n");
                    continue;
                }
                bw.write((char)(parentList.get(j)+'A')+" ");
            }
        }
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Edge implements Comparable<Edge> {
    int planet;
    int cost;
    ArrayList<Integer> parent;
   
    public Edge(int p, int c, ArrayList<Integer> parent) {
        planet = p;
        cost = c;
        this.parent = parent;
    }
   
    public int compareTo(Edge e) {
        return this.cost-e.cost;
    }
}