Number of Ways to Arrive at Destination LeetCode solution in Java

1
class Solution {
2
  class Pair {
3
    int node;
4
    int dist;
5

6
    Pair(int node, int dist) {
7
      this.node = node;
8
      this.dist = dist;
9
    }
10
  }
11

12
  public int countPaths(int n, int[][] roads) {
13
    int mod = (int) Math.pow(10, 9) + 7;
14
    ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
15
    int rows = roads.length;
16
    for (int i = 0; i < n; i++) adj.add(new ArrayList<Pair>());
17
    for (int i = 0; i < rows; i++) {
18
      int from = roads[i][0];
19
      int to = roads[i][1];
20
      int dis = roads[i][2];
21
      adj.get(from).add(new Pair(to, dis));
22
      adj.get(to).add(new Pair(from, dis));
23
    }
24
    PriorityQueue<Pair> pq = new PriorityQueue<>((aa, bb) -> aa.dist - bb.dist);
25
    pq.add(new Pair(0, 0));
26
    long[] ways = new long[n];
27
    ways[0] = 1;
28
    int[] dist = new int[n];
29
    Arrays.fill(dist, Integer.MAX_VALUE);
30
    dist[0] = 0;
31
    while (!pq.isEmpty()) {
32
      Pair p = pq.remove();
33
      int node = p.node;
34
      int dis = p.dist;
35
      for (Pair pa : adj.get(node)) {
36
        if ((dis + pa.dist) < dist[pa.node]) {
37
          ways[pa.node] = ways[node];
38
          dist[pa.node] = dis + pa.dist;
39
          pq.add(new Pair(pa.node, dist[pa.node]));
40
        } else if ((dis + pa.dist) == dist[pa.node]) {
41
          ways[pa.node] += ways[node];
42
          ways[pa.node] = ways[pa.node] % mod;
43
        }
44
      }
45
    }
46
    return (int) ways[n - 1];
47
  }
48
}