DiffPush Tier Graphs · Shortest Path Problems O(n * (E log V)) · O(n + E)
A telco must site its failover depot in the city that would serve the fewest neighbours — measured as cities reachable by any route totalling at most a given latency budget. Ties are broken deliberately: among the quietest candidates, the greatest city id wins. Every city's full reach map is needed before the choice can be made.
Input: An integer n (cities 0..n-1), a list edges where [u, v, w] is a bidirectional weighted link, and distanceThreshold.
Output: Return the city with the fewest reachable cities within distanceThreshold; break ties by choosing the greatest city id.
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 21 <= w, distanceThreshold <= 100Input: {"n":4,"edges":[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],"distanceThreshold":4}
Output: 3
Cities 0 and 3 both reach two neighbours within budget; the tie favours the greater id, 3.
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
City 0 reaches only city 1 within budget 2 — one neighbour, fewer than anyone else.