Reachable Nodes In Subdivided Graph

HardGraphsdijkstra

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You start with an undirected graph of n nodes labeled 0 to n - 1. Each entry edges[i] = [u, v, cnt] describes an edge between u and v that has been **subdivided** by inserting cnt brand-new nodes along it, turning the single edge into a path of cnt + 1 edges. (cnt = 0 leaves the edge as-is.) Starting at node 0, every step moves along one edge of this new, subdivided graph. A node is **reachable** if it can be reached in at most maxMoves steps. Return the number of reachable nodes in the subdivided graph, counting both original nodes and inserted nodes. There are no self-loops and no duplicate edges between the same pair of original nodes; some original nodes may be disconnected from 0.

Examples

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13
All 3 original nodes are within 6 moves (node 1 is 5 moves away via node 2). Edge 0-1 has 7 of its 10 inserted nodes covered (6 from node 0, 1 from node 1), edge 0-2 its 1, and edge 1-2 both of its 2: 3 + 7 + 1 + 2 = 13.
Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output: 23
All 4 original nodes are within 10 moves, and each of the 19 inserted nodes is covered from one end or the other: 4 + 19 = 23.
Input: edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
Output: 1
Node 0 has no edges, so only node 0 itself is reachable.

Constraints

  • 0 <= edges.length <= min(n * (n - 1) / 2, 10^4)
  • edges[i] = [u, v, cnt] with 0 <= u < v < n
  • 0 <= cnt <= 10^4
  • 0 <= maxMoves <= 10^9
  • 1 <= n <= 3000

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dijkstra problems