> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md).

# 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

<https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance>

## Description

There are `n` cities numbered from `0` to `n-1`. Given the array `edges` where `edges[i] = [fromi, toi, weighti]` represents a bidirectional and weighted edge between cities `fromi` and `toi`, and given the integer `distanceThreshold`.

Return the city with the smallest number of cities that are reachable through some path and whose distance is **at most** `distanceThreshold`, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities ***i*** and ***j*** is equal to the sum of the edges' weights along that path.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/01/16/find_the_city_01.png)

```
**Input:** n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
**Output:** 3
**Explanation:** The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/01/16/find_the_city_02.png)

```
**Input:** n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
**Output:** 0
**Explanation:** The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.
```

**Constraints:**

* `2 <= n <= 100`
* `1 <= edges.length <= n * (n - 1) / 2`
* `edges[i].length == 3`
* `0 <= fromi < toi < n`
* `1 <= weighti, distanceThreshold <= 10^4`
* All pairs `(fromi, toi)` are distinct.

## ac1: Floyd-Warshall, O(V^3)

```java
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // MAX_VALUE will cause overflow downstream
            dist[i][i] = 0;
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            dist[u][v] = weight;
            dist[v][u] = weight;
        }
        
        // Standard Floyd-Warshall step: 1) iterate each V; 2) assume k is the mid point from i to j, relax dist[i][j];
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        int res = -1;
        int minReach = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int reach = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue; // Same city
                if (dist[i][j] <= distanceThreshold) {
                    reach++;
                }
            }
            if (reach <= minReach) {
                res = i;
                minReach = reach;
            }
        }
        
        return res;
    }
}

// Floyd-Warshall, O(V^3) time, O(V^2) space. Tricky: use "Integer.MAX_VALUE / 2" to avoid overflow.
```

<https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/discuss/491446/JavaC%2B%2B-Floyd-Warshall's-shortest-path-algorithm-Clean-code>

## ac2: Bellman-Ford, O(VEV)

```java
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // MAX_VALUE will cause overflow downstream
            dist[i][i] = 0;
        }
        
        
        for (int i = 0; i < n; i++) { // Do the following for each V to get a matrix of distance.
            // Bellman-Ford: 1) iterate each V; 2) iterate each edge try to relax u-v, tricky: it's undirected graph, so do u->v and v->u.
            for (int j = 0; j < n; j++) {
                for (int[] edge : edges) {
                    int u = edge[0];
                    int v = edge[1];
                    int weight = edge[2];
                    if (dist[i][u] + weight < dist[i][v]) {
                         dist[i][v] = dist[i][u] + weight;
                    }
                    if (dist[i][v] + weight < dist[i][u]) {
                         dist[i][u] = dist[i][v] + weight;
                    }
                }
            }
        }
        
        int res = -1;
        int minReach = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int reach = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue; // Same city
                if (dist[i][j] <= distanceThreshold) {
                    reach++;
                }
            }
            if (reach <= minReach) {
                res = i;
                minReach = reach;
            }
        }
        
        return res;
    }
}

// Bellman-Ford, O(V*EV) time, O(V^2) space. E = V^2, so it's O(V^4), which is worse than Floyd-Warshall.
```

Shortest Path Faster Algorithm (SPFA) is an improvement of Bellman-Ford:

```java
void spfa(int n, List<int[]>[] adj, int[] dist, int src) {
    Deque<Integer> q = new ArrayDeque<>();
    int[] updateTimes = new int[n];
    q.add(src);
    
    while (!q.isEmpty()) {
        int u = q.removeFirst();
        for (int[] next : adj[u]) {
            int v = next[0];
            int duv = next[1];
            
            if (dist[v] > dist[u] + duv) {
                dist[v] = dist[u] + duv;
                updateTimes[v]++;
                q.add(v);
                if (updateTimes[v] > n) {System.out.println("wrong");}
            }
        }
    }
}
```

## ac3: Dijkstra, O(VElogV)

```java
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE / 2); // MAX_VALUE will cause overflow downstream
            dist[i][i] = 0;
            graph.put(i, new HashMap<>());
        }
        
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            graph.get(u).put(v, weight);
            graph.get(v).put(u, weight);
        }
        
        
        for (int i = 0; i < n; i++) { // Do the following for each V to get a matrix of distance.
            dijkstra(i, dist[i], graph);
        }
        
        int res = -1;
        int minReach = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int reach = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue; // Same city
                if (dist[i][j] <= distanceThreshold) {
                    reach++;
                }
            }
            if (reach <= minReach) {
                res = i;
                minReach = reach;
            }
        }
        
        return res;
    }
    
    private void dijkstra(int src, int[] dist, Map<Integer, Map<Integer, Integer>> graph) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        q.offer(new int[]{src, 0});
        
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int u = curr[0];
            int srcToU = curr[1];
            if (dist[u] < srcToU) continue; // src to u(dist[u]) is already smaller, no point to keep going.
            
            for (int v : graph.get(u).keySet()) {
                if (srcToU + graph.get(u).get(v) < dist[v]) {
                    dist[v] = srcToU + graph.get(u).get(v);
                    q.offer(new int[]{v, dist[v]});
                }
            }
        }
    }
}

// Dijkstra, O(V*ElogV) time, O(V^2) space. E = V^2, so it's O(V^3logV), which is worse than Floyd-Warshall.
// Tricky: you can use boolean[] visited to avoid loop, but it's better to rely on their weight, i.e. if (dist[u] < srcToU) continue; 
```