(Hacker Rank) Dijkstra: Shortest Reach 2 - Solution

Link to the problem: https://www.hackerrank.com/challenges/dijkstrashortreach

Once the problem asks us to find the shortest distance from a node to all the other nodes, and all the edges in the graph are weighted, a good way to solve this problem is using Dijkstra.



import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
   
    public static Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost-e2.cost;
        }   
    };
   
    public static void dijkstra(int start, int[] shortestPaths) {
        Queue<Edge> queue = new PriorityQueue<>(16, costComparator);
        queue.add(new Edge(start, 0));
       
        HashSet<Integer> visited = new HashSet<>();
       
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currNode = curr.node;
            int currCost = curr.cost;
           
            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);
           
            shortestPaths[currNode] = currCost;
           
            ArrayList<Edge> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                queue.add(new Edge(reachNodes.get(i).node, reachNodes.get(i).cost+currCost));
            }
        }
    }
   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
           
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numNodes = sc.nextInt();
            int numEdges = sc.nextInt();
       
            adjList = new HashMap<>();
            for (int j = 1; j <= numNodes; j++) {
                adjList.put(j, new ArrayList<Edge>());
            }
           
            for (int j = 0; j < numEdges; j++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                int c = sc.nextInt();
               
                adjList.get(n1).add(new Edge(n2, c));
                adjList.get(n2).add(new Edge(n1, c));
            }
           
            int start = sc.nextInt();
           
            int[] shortestPaths = new int[numNodes+1];
            for (int j = 1; j <= numNodes; j++) {
                shortestPaths[j] = -1;
            }
            dijkstra(start, shortestPaths);
           
            for (int j = 1; j <= numNodes; j++) {
                if (j == start) {
                    continue;
                }
                if (j == numNodes) {
                    System.out.println(shortestPaths[j]);
                    continue;
                }
                System.out.print(shortestPaths[j]+" ");
            }
        }
    }
}

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