772. Fewest Reachable City
A courier company serves n towns numbered 0 to n - 1. Each entry edges[i] = [u, v, w] is a two-way road of length w between towns u and v. A courier based in town s can serve town t when the shortest road distance from s to t is at most threshold; roads can be combined freely along the way.
For every town, count how many other towns its courier can serve (a town never counts itself). Return the town with the smallest count. If several towns tie for the smallest count, return the one with the largest number.
Example 1
- Input:
- n = 5edges = [[0,1,2],[1,2,3],[2,3,1],[3,4,4],[1,3,5]]threshold = 6
- Output:
- 4
- Explanation:
The reach counts for towns 0..4 are 3, 3, 4, 4 and 2 (town 4 reaches only towns 3 and 2, at distances 4 and 5), so town 4 has the fewest.
Example 2
- Input:
- n = 4, edges = [[0,1,3],[1,2,3],[2,3,3]], threshold = 3
- Output:
- 3
- Explanation:
The end towns 0 and 3 each reach one neighbour while the middle towns reach two; towns 0 and 3 tie for fewest, so the larger number 3 is returned.
Example 3
- Input:
- n = 3, edges = [[0,1,10],[1,2,10]], threshold = 5
- Output:
- 2
- Explanation:
Every road is longer than the threshold, so every town serves nobody; all tie at 0 and the largest number 2 wins.
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ edges.length ≤ min(5000, n * (n - 1) / 2)
- 0 ≤ u, v < n, u ≠ v, and each pair of towns appears at most once
- 1 ≤ w ≤ 104
- 1 ≤ threshold ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(n * (m + n) log n)
- Space
- O(n + m)