(UVA) Route Change - Solution

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

Given a start position, the problem asks us to find the minimum total toll cost for the vehicle to reach the destination city. For this reason, the code below used Dijkstra's algorithm to find the solution.


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

class Main {
    public ArrayList<ArrayList<Edge>> adjList;
    public int citiesServiceRoute;
   
    public int dijkstra(int start, int end) {
        Queue<Edge> queue = new PriorityQueue<>();
        queue.add(new Edge(start, 0));
       
        HashSet<Integer> visited = new HashSet<>();
       
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currCity = curr.city;
            int currCost = curr.cost;
           
            if (visited.contains(currCity)) {
                continue;
            }
            visited.add(currCity);
           
            if (currCity == end) {
                return currCost;
            }
           
            ArrayList<Edge> reachable = adjList.get(currCity);
            for (int i = 0; i < reachable.size(); i++) {
                // if the vehicle reached one of the cities that make up its service route
                if (currCity < citiesServiceRoute) {
                    if (reachable.get(i).city == currCity+1) { // add to the queue only if the node is the next node to the current node
                        queue.add(new Edge(reachable.get(i).city, currCost+reachable.get(i).cost));
                    }
                } else {
                    queue.add(new Edge(reachable.get(i).city, currCost+reachable.get(i).cost));
                }
            }
        }
       
        return -1;
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numCities = sc.nextInt();
        int numRoads = sc.nextInt();
        citiesServiceRoute = sc.nextInt();
        int cityRepair = sc.nextInt();
        while (numCities != 0 || numRoads != 0 || citiesServiceRoute != 0 || cityRepair != 0) {
            adjList = new ArrayList<>();
            for (int i = 0; i < numCities; i++) {
                adjList.add(new ArrayList<Edge>());
            }
           
            for (int i = 0; i < numRoads; i++) {
                int c1 = sc.nextInt();
                int c2 = sc.nextInt();
                int cost = sc.nextInt();
               
                adjList.get(c1).add(new Edge(c2, cost));
                adjList.get(c2).add(new Edge(c1, cost));
            }
           
            bw.write(dijkstra(cityRepair, citiesServiceRoute-1)+"\n");
       
            numCities = sc.nextInt();
            numRoads = sc.nextInt();
            citiesServiceRoute = sc.nextInt();
            cityRepair = sc.nextInt();
        }
          
        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 city;
    int cost;
   
    public Edge (int ci, int co) {
        city = ci;
        cost = co;
    }
   
    public int compareTo(Edge e) {
        return this.cost-e.cost;
    }
}