Given a weighted undirected graph and a distance threshold, return the city with the smallest number of other cities reachable within that threshold. Break ties by choosing the city with the greatest index. Pattern focus: Floyd-Warshall. This problem is a classic all-pairs shortest path application.
n = city count, edges = weighted undirected roads, distanceThreshold = maximum allowed distance
city index with the smallest reachable city count under the threshold
Example 1:
Input:
n = 4 edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] distanceThreshold = 4
Output:
3
Explanation:
City 3 reaches the fewest cities within the threshold, and ties favor the largest index.
Example 2:
Input:
n = 5 edges = [[0,1,2],[1,2,2],[2,3,2],[3,4,2]] distanceThreshold = 2
Output:
4
Explanation:
The farthest city has the smallest reachable count under the threshold.
Example 3:
Input:
n = 3 edges = [[0,1,5],[1,2,5]] distanceThreshold = 10
Output:
2
Explanation:
All cities are equally reachable, so choose the largest index.