Hub Vertices Within a Radius
Problem statement
A graph has n nodes numbered from 0 through n-1. Some nodes are marked as hubs. Given a starting node and a radius, return all marked hubs whose shortest-path distance from the start is at most the radius.
For this exercise, the graph is undirected and edges have nonnegative integer distances. Each row [u,v,w] in edges connects u and v in both directions with distance w. Use w=1 for the reported unit-distance version; other nonnegative weights represent its weighted-distance follow-up. hubNodes lists the node IDs whose isHub field is true.
For this exercise, the radius is inclusive, a starting hub is included at distance zero, and unreachable hubs are excluded. Return node IDs in increasing numeric order, not distance order. The graph may be disconnected, zero-weight edges are allowed, and an empty hub list returns an empty array. These direction, weight-domain, boundary, ordering and input-representation choices complete details not specified in the report.
Function
nearbyHubs(n: int, edges: int[][], hubNodes: int[], start: int, radius: int) → int[]Examples
Example 1
n = 5edges = [[0,1,1],[1,2,1],[0,3,1],[3,4,1]]hubNodes = [2,3,4]start = 0radius = 1return = [3]The marked node 3 is one unit from node 0. Marked nodes 2 and 4 are each two units away, so radius 1 returns [3].
Example 2
n = 5edges = [[0,1,9],[0,2,2],[2,1,2],[1,3,1]]hubNodes = [1,3,4]start = 0radius = 5return = [1,3]Node 1 is reached more cheaply along 0 → 2 → 1, with cost 4, than by its direct edge of cost 9. Node 3 has shortest distance 5 and is included at the boundary. Node 4 is unreachable. Return [1,3].
Constraints
1 <= n <= 2000 <= edges.length <= 2000; every edge has exactly three entries[u,v,w].0 <= edges[i][j] <= 1000000. Endpoints satisfy u < n and v < n; u != v. Each unordered endpoint pair occurs at most once.0 <= hubNodes.length <= 200. Hub IDs are distinct and satisfy0 <= hubNodes[i] < n.0 <= start < n0 <= radius <= 1000000000