1035. Find the City with Smallest Reachable Neighbours

Given n cities and undirected weighted edges [u, v, w], and a distanceThreshold, find the city with the fewest other cities reachable within a total distance <= threshold. If several tie, return the one with the greatest label. The input is JSON {n, edges, distanceThreshold}.

Input: JSON {n, edges, distanceThreshold} with edges [u, v, w].

Output: Integer — the chosen city label.

Examples

Input: {"n":4,"edges":[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],"distanceThreshold":4}
Output: 3
Explanation: City 3 reaches the fewest within 4.

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: Tie broken toward the smaller count.

Input: {"n":2,"edges":[[0,1,5]],"distanceThreshold":3}
Output: 1
Explanation: Neither reaches the other; pick larger label.

Constraints

• 2<=n<=100
• undirected

Asked by