Reachable Nodes in Subdivided Graph — Dijkstra

Problem

A graph where each edge (u,v,cnt) has cnt new nodes inserted. Starting from node 0 with M moves, count all reachable original and subdivided nodes.

Approach — Dijkstra + Edge Budget

Dijkstra gives max remaining moves rem[v] after reaching each original node. For each edge (u,v,cnt): subdivisions reachable = min(cnt, rem[u]) + min(cnt, rem[v]), but capped at cnt total.

Time: O(E log V) | Space: O(V+E)

Solutions

Python

import heapq
from collections import defaultdict
class Solution:
    def reachableNodes(self, edges: list[list[int]], maxMoves: int, n: int) -> int:
        adj=defaultdict(dict)
        for u,v,cnt in edges: adj[u][v]=cnt; adj[v][u]=cnt
        dist=[-1]*n; dist[0]=maxMoves
        heap=[(-maxMoves,0)]
        while heap:
            d,u=heapq.heappop(heap); d=-d
            if d<dist[u]: continue
            for v,cnt in adj[u].items():
                rem=d-cnt-1
                if rem>=0 and rem>dist[v]:
                    dist[v]=rem; heapq.heappush(heap,(-rem,v))
        ans=sum(1 for d in dist if d>=0)
        for u,v,cnt in edges:
            reached=0
            if dist[u]>=0: reached+=min(cnt,dist[u])
            if dist[v]>=0: reached+=min(cnt,dist[v])
            ans+=min(cnt,reached)
        return ans

Complexity

Time: O(E log V) | Space: O(V+E)