Graphs
Find City with Fewest Reachable
DESCRIPTION (inspired by Leetcode.com)
A regional planning committee wants to identify the most "isolated" city in a road network. Given n cities connected by bidirectional roads with varying distances, find the city that can reach the fewest other cities within a given distance threshold.
If multiple cities have the same minimum count, return the city with the highest number.
Note: The distance between two cities is the shortest path distance considering all possible routes.
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 can only reach city 1 (distance 4) within the threshold. Cities 0 and 2 can each reach 2 cities, and city 1 can reach 3 cities. City 3 has the fewest reachable.
Example 2:
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: With threshold 2, city 0 can only reach city 1 (distance 2). Other cities can reach more neighbors. City 0 has the fewest reachable.