Number of Restricted Paths From First to Last Node LeetCode solution in Java

1
class Solution {
2
  int dp[];
3

4
  // We use memoization
5
  public int countRestrictedPaths(int n, int[][] edges) {
6
    int[] dist = new int[n + 1];
7
    dp = new int[n + 1];
8
    Arrays.fill(dp, -1);
9
    Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
10
    // Create the graph from input edges
11
    for (int[] e : edges) {
12
      graph.putIfAbsent(e[0], new HashMap<>());
13
      graph.putIfAbsent(e[1], new HashMap<>());
14
      graph.get(e[0]).put(e[1], e[2]);
15
      graph.get(e[1]).put(e[0], e[2]);
16
    }
17
    // Single source shortest distance - something like Dijkstra's
18
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
19
    int[] base = new int[2];
20
    base[0] = n;
21
    pq.offer(base);
22
    while (!pq.isEmpty()) {
23
      int[] currNode = pq.poll();
24

25
      for (Map.Entry<Integer, Integer> neighbour : graph.get(currNode[0]).entrySet()) {
26
        int node = neighbour.getKey();
27
        int d = neighbour.getValue() + currNode[1];
28
        if (node == n) continue;
29
        // Select only those neighbours, whose new distance is less than existing distance
30
        // New distance = distance of currNode from n + weight of edge between currNode and
31
        // neighbour
32

33
        if (dist[node] == 0 || d < dist[node]) {
34
          int[] newNode = new int[2];
35
          newNode[0] = node;
36
          newNode[1] = d;
37
          pq.offer(newNode);
38
          dist[node] = d;
39
        }
40
      }
41
    }
42

43
    return find(1, graph, n, dist);
44
  }
45

46
  // This method traverses all the paths from source node to n though it's neigbours
47
  private int find(int node, Map<Integer, Map<Integer, Integer>> graph, int n, int[] dist) {
48
    if (node == n) {
49
      return 1;
50
    }
51

52
    // Memoization avoid computaion of common subproblems.
53
    if (dp[node] != -1) return dp[node];
54

55
    int ans = 0;
56
    for (Map.Entry<Integer, Integer> neighbour : graph.get(node).entrySet()) {
57
      int currNode = neighbour.getKey();
58
      int d = dist[currNode];
59
      if (dist[node] > d) {
60
        ans = (ans + find(currNode, graph, n, dist)) % 1000000007;
61
      }
62
    }
63

64
    return dp[node] = ans;
65
  }
66
}