448. Find the city with the smallest number of neighbors
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 distance Threshold. Find out a city with the smallest number of cities that are reachable through some path and whose distance is at most Threshold Distance.
If there are multiple such cities, our answer will be the city with the greatest number.
Example 1:
Input : N=4, M=4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation:
The adjacent cities for each city at a distanceThreshold 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]
Here, City 0 and City 3 have a minimum number of cities
i.e. 2 within distanceThreshold. So, the result will be the
city with the largest number. So, the answer is City 3.
Example 2:
Input : N=3, M=2, edges = [[0,1,1],[0,2,3]], distanceThreshold = 2
Output: 2
Explanation:
City 0 -> City 1,
City 1 → City 0,
City 2 → no City
Hence, 2 is the answer.
Now Your Turn!
Pick the correct output for the given inputInput: N = 3, M = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], distanceThreshold = 2
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 ≤ n ≤ 100
- 1 <= m <= n*(n-1)/2
- length(edges[i]) == 3
- 0 <= fromi < toi < n
- 1 <= weighti , distanceThreshold <= 104
- All pairs (fromi, toi) are distinct