Best Telescope Site

Problem Given n sites connected by weighted bidirectional edges and a distance threshold, find the site with the fewest other sites reachable within the threshold; break ties by the largest index.

Input / Output

• Input: n, edge list (u, v, w), int distanceThreshold.
• Output: the chosen site index.

Constraints

• n <= 100 in the classic version — all-pairs shortest paths is intended.

Example

• n=4, edges [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], threshold=4 → site 3 (sites 0 and 3 both reach 2 others; pick the larger index).

Expected approach

• Floyd–Warshall: dist[i][j] via intermediate-node relaxation, O(n^3) time / O(n^2) space — trivial at n=100. Then count per node the neighbors with dist <= threshold and select min count with max index. Alternative: Dijkstra from every node, O(n * E log V) — worth mentioning for sparse graphs / larger n.