The problem. There are n cities, 0 to n - 1, joined by two-way roads edges[i] = [from, to, weight]. For each city, count the other cities you can reach with a shortest distance of at most distanceThreshold. Return the city with the smallest count; if there's a tie, return the one with the largest number.
n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 -> 3
n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 -> 0Every city needs its distance to every other city: shortest paths between all pairs. With n cities there are n² answers, so one fast way is to fill an n × n table.
Floyd-Warshall fills it with a short dynamic program. Start with dist[i][j] = the road between i and j (or ∞). Then, for each city k in turn, ask of every pair: *is it shorter to go from i to j through k?* — dist[i][k] + dist[k][j] < dist[i][j]. After round k, dist[i][j] is the shortest path that may stop only at cities 0..k in between. After the last round every city is allowed, so every entry is exact.
The order of the loops matters: k must be the outer loop. Each round builds on paths that already use the cities before k. Three nested loops over n give O(n³) — great for a few hundred cities, and it handles directed roads and even negative weights (as long as there's no negative cycle).
Run Dijkstra (Pattern 8) once from each city. Stop as soon as the popped distance passes the threshold — everything after it is further still — and count the cities settled before that.
function findTheCity(n, edges, distanceThreshold) { const adj = Array.from({ length: n }, () => []); for (const [u, v, w] of edges) { adj[u].push([v, w]); adj[v].push([u, w]); } const reachableFrom = (src) => { // Dijkstra from src, counting cities within the threshold const dist = new Array(n).fill(Infinity); dist[src] = 0; const heap = new Heap((a, b) => a[0] - b[0]); heap.push([0, src]); let count = 0; while (heap.size() > 0) { const [d, u] = heap.pop(); if (d > dist[u]) continue; if (d > distanceThreshold) break; // everything left is even further if (u !== src) count++; for (const [v, w] of adj[u]) { if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]); } } } return count; }; let answer = -1, fewest = Infinity; for (let i = 0; i < n; i++) { const reachable = reachableFrom(i); if (reachable <= fewest) { // <= so a tie goes to the larger city number fewest = reachable; answer = i; } } return answer;}Time O(n · E log n), space O(n + E). n runs of Dijkstra, each O(E log n). On sparse road maps this can beat Floyd-Warshall; on dense ones (E close to n²) it's slower.
Build the n × n table, run the three loops with k outermost, then count each row's entries within the threshold. Walking cities in increasing order with <= makes ties go to the larger number automatically.
Each round lets every path stop at one more city. Watch the row and column of city k feed the updates.
function findTheCity(n, edges, distanceThreshold) { const dist = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity))); for (const [u, v, w] of edges) { dist[u][v] = w; // roads go both ways dist[v][u] = w; } for (let k = 0; k < n; k++) { // now allow city k as a stop in between 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, fewest = Infinity; for (let i = 0; i < n; i++) { let reachable = 0; for (let j = 0; j < n; j++) if (i !== j && dist[i][j] <= distanceThreshold) reachable++; if (reachable <= fewest) { // <= so a tie goes to the larger city number fewest = reachable; answer = i; } } return answer;}Time O(n³), space O(n²). n rounds over all n² pairs, and one n × n table. In Java and C++, use a large finite "infinity" like 10⁹ so that adding two of them doesn't overflow.
With at most 100 cities, both are instant. Floyd-Warshall is shorter to write and hard to get wrong, which is why it's the classic answer whenever every pair is needed and n is small.
k anywhere but outermost gives wrong distances.a / b = 2 and b / c = 3 give a / c: all-pairs over a graph where you multiply along paths.