Number of Ways to Arrive at Destination LeetCode solution in JavaScript

1
/**
2
 * @param {number} n
3
 * @param {number[][]} roads
4
 * @return {number}
5
 */
6
var countPaths = function (n, roads) {
7
  let adj = {},
8
    dist = Array(n).fill(Infinity),
9
    minHeap = new MinHeap(),
10
    count = Array(n).fill(1);
11

12
  //CREATE ADJ MATRIX
13
  for (let [from, to, weight] of roads) {
14
    adj[from] = adj[from] || [];
15
    adj[from].push([to, weight]);
16
    adj[to] = adj[to] || [];
17
    adj[to].push([from, weight]);
18
  }
19

20
  //PUT START IN QUEUE
21
  dist[n - 1] = 0;
22
  minHeap.enqueue(n - 1, 0);
23

24
  while (minHeap.getSize()) {
25
    let [node, curDist] = minHeap.dequeue();
26
    let children = adj[node] || [];
27
    for (let [childNode, childWeight] of children) {
28
      //IF PATH ALREADY FOUND WITH THIS VALUE THEN ADD COUNT REACHED UNTIL NOW
29
      if (curDist + childWeight === dist[childNode]) {
30
        count[childNode] = (count[childNode] + count[node]) % 1000000007;
31
      } //IF NOT PATH FOUND YET THEN ADD COUNT OF WAYS TO THE NODE WE CAME FROM
32
      else if (curDist + childWeight < dist[childNode]) {
33
        count[childNode] = count[node];
34
        dist[childNode] = curDist + childWeight;
35
        minHeap.enqueue(childNode, dist[childNode]);
36
      }
37
    }
38
  }
39
  return count[0];
40
};
41

42
class MinHeap {
43
  constructor(list = []) {
44
    this.tree = [null];
45
    this.list = list;
46
    this.build();
47
  }
48

49
  build() {
50
    for (let [val, priority] of this.list) this.enqueue(val, priority);
51
  }
52

53
  swap(pos1, pos2) {
54
    [this.tree[pos1], this.tree[pos2]] = [this.tree[pos2], this.tree[pos1]];
55
  }
56

57
  enqueue(val, priority) {
58
    this.tree[this.tree.length] = [val, priority];
59
    let i = this.tree.length - 1,
60
      parent = ~~(i / 2);
61
    while (i > 1) {
62
      if (this.tree[parent][1] > this.tree[i][1]) this.swap(parent, i);
63
      i = parent;
64
      parent = ~~(i / 2);
65
    }
66
  }
67

68
  dequeue() {
69
    let size = this.tree.length - 1,
70
      pos = 1;
71
    if (!size) return;
72
    let last = this.tree.pop(),
73
      deleted = this.tree[pos];
74
    if (!deleted && last) return last;
75
    this.tree[pos] = last;
76
    this.heapify(pos);
77
    return deleted;
78
  }
79

80
  heapify(pos) {
81
    if (pos > this.tree.length) return;
82
    let leftPos = 2 * pos,
83
      rightPos = 2 * pos + 1;
84
    let left = this.tree[leftPos] ? this.tree[leftPos][1] : Infinity;
85
    let right = this.tree[rightPos] ? this.tree[rightPos][1] : Infinity,
86
      minVal = null,
87
      minIndex = null;
88
    if (left < right) {
89
      minVal = left;
90
      minIndex = leftPos;
91
    } else {
92
      minVal = right;
93
      minIndex = rightPos;
94
    }
95
    if (this.tree[pos][1] > minVal) {
96
      this.swap(pos, minIndex);
97
      this.heapify(minIndex);
98
    }
99
  }
100

101
  getTree() {
102
    console.log(this.tree.slice(1));
103
  }
104

105
  getSize() {
106
    return this.tree.length - 1;
107
  }
108
}