City With the Fewest Reachable Neighbours
There are n cities numbered 0 to n - 1. The list edges holds the roads: edges[i] = [u, v, w] is a road between city u and city v of length w. You can drive a road in both directions.
The distance between two cities is the length of the shortest route between them, which may use several roads. For each city, count the other cities whose distance from it is at most threshold.
Return the city with the smallest count. If several cities share the smallest count, return the one with the largest number.
Note
- A city that cannot be reached at all is not counted.
- A direct road is not always the shortest route. Two short roads can be shorter than one long road.
Hint: the graph is small, so you can find the shortest distance between every pair of cities (for example with the Floyd–Warshall method, or by running Dijkstra from every city). Then count for each city.
Examples
Example 1
- Input:
- 5, [[0,1,2],[1,2,3],[2,3,1],[0,3,9],[3,4,7]], 5
- Output:
- 4
Within distance 5: city 0 reaches 1 and 2 (2 cities), city 1 reaches 0, 2 and 3 (3), city 2 reaches 0, 1 and 3 (3), city 3 reaches 1 and 2 (2), and city 4 reaches none (0). City 4 has the smallest count.
Example 2
- Input:
- 4, [[0,1,4],[1,2,4],[2,3,4]], 4
- Output:
- 3
Cities 0 and 3 can each reach one other city, and cities 1 and 2 can each reach two. Cities 0 and 3 share the smallest count, so return the larger number, 3.
Example 3
- Input:
- 3, [[0,1,10],[0,2,1],[2,1,1]], 2
- Output:
- 2
The road 0-1 has length 10, but the route 0 → 2 → 1 has length 2. So every city reaches both others within 2. All counts are equal, so return the largest city, 2.
Constraints
2 <= n <= 120 <= edges.length <= n * (n - 1) / 2edges[i] = [u, v, w]with0 <= u, v < n,u != vand1 <= w <= 20- No pair of cities has more than one road.
0 <= threshold <= 60
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.