Minimum Cost to Reach Destination in Time LeetCode solution in Java

1
class Solution {
2
  record Node(int i, int t) {}
3

4
  record Cell(int i, int t, int c) {}
5

6
  public int minCost(int maxTime, int[][] edges, int[] fees) {
7
    int n = fees.length;
8

9
    // create the adjacency list graph
10
    List<Node>[] g = new List[n];
11
    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
12
    for (var e : edges) {
13
      g[e[0]].add(new Node(e[1], e[2]));
14
      g[e[1]].add(new Node(e[0], e[2]));
15
    }
16

17
    // Dijkstra
18
    Queue<Cell> q = new PriorityQueue<>((a, b) -> a.c == b.c ? a.t - b.t : a.c - b.c);
19
    int[] T = new int[n]; // 1. visited: de-dup 2. de-dup on worst time
20

21
    q.offer(new Cell(0, 0, fees[0]));
22
    Arrays.fill(T, maxTime + 1);
23
    T[0] = 0;
24

25
    while (!q.isEmpty()) {
26
      var cur = q.poll();
27
      if (cur.i == n - 1) return cur.c;
28

29
      for (var nei : g[cur.i]) {
30
        int t2 = cur.t + nei.t;
31
        if (t2 >= T[nei.i]) continue; // if time is worst, no reason to continue
32
        T[nei.i] = t2;
33
        q.offer(new Cell(nei.i, t2, cur.c + fees[nei.i]));
34
      }
35
    }
36

37
    return -1;
38
  }
39
}