Find the City
With Fewest Neighbours Within Threshold Distance

Problem Statement

Given n cities numbered from 0 to n - 1, and an array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional road between cities fromi and toi with travel distance weighti, you are also given a distance threshold distanceThreshold.

Your task is to find the city with the smallest number of other cities that can be reached from it through any path such that the total distance is less than or equal to distanceThreshold.

If there are multiple cities with the same minimal number of reachable neighbours, return the city with the greatest number.

Algorithm Steps

1. Initialize a 2D matrix dist with infinity, except dist[i][i] = 0.
2. Fill in direct distances from the edges input.
3. Run the Floyd-Warshall algorithm:
   1. For each intermediate node k, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
4. For each city, count the number of other cities it can reach with distance ≤ threshold.
5. Return the city with the fewest reachable cities (use max index in case of tie).

Code

function findTheCity(n, edges, distanceThreshold) {
  const INF = 1e9;
  const dist = Array.from({ length: n }, () => Array(n).fill(INF));

  for (let i = 0; i < n; i++) dist[i][i] = 0;
  for (const [u, v, w] of edges) {
    dist[u][v] = w;
    dist[v][u] = w;
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  let answer = -1;
  let minReachable = n;

  for (let i = 0; i < n; i++) {
    let count = 0;
    for (let j = 0; j < n; j++) {
      if (i !== j && dist[i][j] <= distanceThreshold) count++;
    }
    if (count <= minReachable) {
      minReachable = count;
      answer = i;
    }
  }

  return answer;
}

console.log(findTheCity(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)); // Output: 3
console.log(findTheCity(5, [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], 2)); // Output: 0