#1334
Find the City With the Smallest Number of Neighbors at a Threshold Distance
pupil · 530 · lc medium +28 · verified · 72.2% accepted · 3,598 likes · top 81%
Description
There are n cities numbered 0 to n-1. Each element of edges is [fromi, toi, weighti], a bidirectional weighted connection. For each city, count how many other cities are reachable via some path whose total weight is at most distanceThreshold. Return the city with the fewest reachable neighbors; on a tie, return the city with the greatest index.
The distance of a path is the sum of the weights of its edges.
Example 1:
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: 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 = 2
Output: 0
Explanation: 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.
Code
1
2
3