Find the City with the Smallest Number of Neighbours
Medium · shortest path
A region has n towns, numbered 0 to n - 1. The two-way roads are given as a list roads of triples [a, b, length]: a road between towns a and b that is length kilometres long.
A town counts as a neighbour of another town if the shortest way between them, along any chain of roads, is at most limit kilometres. The shortest way may pass through other towns. A town is not its own neighbour.
Return the town that has the fewest neighbours. If several towns tie for the fewest, return the one with the largest number.
No road joins a town to itself, and no two roads join the same pair of towns. A town with no road to it has no neighbours.
Examples
Example 1
Input: n = 4, roads = [[0, 1, 3], [1, 2, 1], [2, 3, 4], [0, 3, 9]], limit = 4
Output: 3
Within 4 km, town 0 reaches towns 1 and 2, town 1 reaches 0 and 2, town 2 reaches 0, 1 and 3, but town 3 reaches only town 2 (town 1 is 5 km away).
Example 2
Input: n = 4, roads = [[0, 1, 3], [1, 2, 1], [2, 3, 4], [0, 3, 9]], limit = 5
Output: 3
Towns 0 and 3 both have two neighbours (town 3 now reaches towns 2 and 1), while towns 1 and 2 have three. Towns 0 and 3 tie, and the larger number wins.
Example 3
Input: n = 3, roads = [], limit = 10
Output: 2
Nobody has a neighbour, so all towns tie and the largest number wins.
Constraints
- 2 <= n <= 100
- 0 <= len(roads) <= n * (n - 1) / 2
- Each road is [a, b, length] with 0 <= a, b < n, a != b and 1 <= length <= 10^4.
- 1 <= limit <= 10^4