Find the City With the Smallest Number of Neighbors at a Threshold Distance LeetCode solution in JavaScript

1
var findTheCity = function (n, edges, distanceThreshold) {
2
  const dp = Array.from({ length: n }, (_, i) => {
3
    return Array.from({ length: n }, (_, j) => (i == j ? 0 : Infinity));
4
  });
5

6
  for (let edge of edges) {
7
    const [a, b, w] = edge;
8
    dp[a][b] = dp[b][a] = w;
9
  }
10

11
  // k is intermediate node
12
  for (let k = 0; k < n; k++) {
13
    // fix distances from i to other nodes with k as intermediate
14
    for (let i = 0; i < n; i++) {
15
      if (i == k || dp[i][k] == Infinity) continue;
16
      for (let j = i + 1; j < n; j++) {
17
        dp[i][j] = dp[j][i] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
18
      }
19
    }
20
  }
21

22
  let city = -1,
23
    minCity = n;
24
  for (let i = 0; i < n; i++) {
25
    let count = 0;
26
    for (let j = 0; j < n; j++) {
27
      if (i == j) continue;
28
      if (dp[i][j] <= distanceThreshold) count++;
29
    }
30
    if (count <= minCity) {
31
      minCity = count;
32
      city = i;
33
    }
34
  }
35

36
  return city;
37
};