1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Medium

2K

75

There are `n`

cities numbered from `0`

to `n-1`

. Given the array `edges`

where `edges[i] = [from`

represents a bidirectional and weighted edge between cities _{i}, to_{i}, weight_{i}]`from`

and _{i}`to`

, and given the integer _{i}`distanceThreshold`

.

Return the city with the smallest number of cities that are reachable through some path and whose distance is **at most** `distanceThreshold`

, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities * i* and

**Example 1:**

Input:n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4Output:3Explanation:The figure above describes the graph. The neighboring cities at a distanceThreshold = 4 for each city are: City 0 -> [City 1, City 2] City 1 -> [City 0, City 2, City 3] City 2 -> [City 0, City 1, City 3] City 3 -> [City 1, City 2] Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

**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 = 2Output:0Explanation:The figure above describes the graph. The neighboring cities at a distanceThreshold = 2 for each city are: City 0 -> [City 1] City 1 -> [City 0, City 4] City 2 -> [City 3, City 4] City 3 -> [City 2, City 4] City 4 -> [City 1, City 2, City 3] The city 0 has 1 neighboring city at a distanceThreshold = 2.

**Constraints:**

`2 <= n <= 100`

`1 <= edges.length <= n * (n - 1) / 2`

`edges[i].length == 3`

`0 <= from`

_{i}< to_{i}< n`1 <= weight`

_{i}, distanceThreshold <= 10^4- All pairs
`(from`

are distinct._{i}, to_{i})

Accepted

64.8K

Submissions

117.1K

Acceptance Rate

55.4%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved