content: // https://leetcode.com/problems/network-delay-time
  // Single source shortest path algorithm (Dijkstra's Algorithm)
  // T: O(E log(N) for dijkstra + N for searching max val)
  // S: O(E + N)
  
  import java.util.Arrays;
  import java.util.Comparator;
  import java.util.HashMap;
  import java.util.Map;
  import java.util.PriorityQueue;
  import java.util.Queue;
  
  public class NetworkDelayTime {
      private record Node(int value, long time) { }
  
      public int networkDelayTime(int[][] times, int n, int k) {
          final Map<Integer, Map<Integer, Integer>> graph = createDirectedGraphFrom(times);
          final long[] minTimeTaken = getMinTimeTakenArray(n, k);
          final Queue<Node> queue = new PriorityQueue<Node>(Comparator.comparing(Node::time));
          queue.add(new Node(k, 0));
  
          while (!queue.isEmpty()) {
              Node node = queue.poll();
              if (!graph.containsKey(node.value)) continue;
              Map<Integer, Integer> vertexNode = graph.get(node.value);
              for (int adjacent : vertexNode.keySet()) {
                  if (minTimeTaken[node.value - 1] + vertexNode.get(adjacent) < minTimeTaken[adjacent - 1]) {
                      minTimeTaken[adjacent - 1] = minTimeTaken[node.value - 1] + vertexNode.get(adjacent);
                      queue.add(new Node(adjacent, minTimeTaken[adjacent - 1]));
                  }
              }
          }
  
          return allAreReached(minTimeTaken) ? (int) Arrays.stream(minTimeTaken).max().getAsLong() : -1;
      }
  
      private Map<Integer, Map<Integer, Integer>> createDirectedGraphFrom(int[][] times) {
          final Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
          for (int[] time : times) {
              int start = time[0];
              int destination = time[1];
              int delay = time[2];
  
              graph.putIfAbsent(start, new HashMap<>());
              graph.get(start).put(destination, delay);
          }
          return graph;
      }
  
      private long[] getMinTimeTakenArray(int length, int start) {
          long[] array = new long[length];
          for (int i = 0 ; i < length ; i++) {
              array[i] = Integer.MAX_VALUE;
          }
          array[start - 1] = 0;
          return array;
      }
  
      private boolean allAreReached(long[] array) {
          for (long val : array) {
              if (val == Integer.MAX_VALUE) return false;
          }
          return true;
      }
  }
  