Find the city that can reach the fewest other cities within a given distance limit, breaking ties by choosing the largest city index.
You are given an undirected weighted graph with cities labeled from $0n - 1$. Each road connects two cities and has a travel distance.
A city is considered able to reach another city if the shortest distance between them is less than or equal to a given threshold distance.
Return the city that can reach the smallest number of other cities within the threshold distance. If multiple cities have the same minimum count, return the city with the largest index.
The shortest distance from a city to itself is $0$, but it should not be counted as a reachable neighbor.
Input Format
n: number of citiesedges: list of undirected roads, where each road is[u, v, w]distanceThreshold: maximum allowed shortest-path distance
Output Format
Return the index of the city with the smallest number of reachable neighbors within distanceThreshold. If tied, return the largest index.
Constraints
- Roads are undirected and weighted with non-negative distances
- The graph may be disconnected
- Count only other cities, not the city itself
Example 1
Input
n = 4 edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] distanceThreshold = 4
Output
3
Explanation
Reachable city counts within distance 4 are: 0 -> 2, 1 -> 3, 2 -> 3, 3 -> 2. The minimum count is 2, shared by cities 0 and 3, so return the larger index: 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.