Reachable Nodes In Subdivided Graph

lcpy gen -n 882   # by problem number
lcpy gen -s reachable_nodes_in_subdivided_graph   # by problem name

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13
Explanation: The edge subdivisions are shown in the image above.
The nodes that are reachable are highlighted in yellow.

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output: 23

Input: edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
Output: 1
Explanation: Node 0 is disconnected from the rest of the graph, so only node 0 is reachable.

import heapq


class Solution:
    # Time: O(E log V)
    # Space: O(V + E)
    def reachable_nodes(self, edges: list[list[int]], max_moves: int, n: int) -> int:
        adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
        for u, v, cnt in edges:
            adj[u].append((v, cnt))
            adj[v].append((u, cnt))

        unreachable = max_moves + 1
        dist = [unreachable] * n
        dist[0] = 0
        heap: list[tuple[int, int]] = [(0, 0)]
        while heap:
            d, node = heapq.heappop(heap)
            if d > dist[node]:
                continue
            for nxt, cnt in adj[node]:
                nd = d + cnt + 1
                if nd < dist[nxt]:
                    dist[nxt] = nd
                    heapq.heappush(heap, (nd, nxt))

        reachable = sum(1 for d in dist if d <= max_moves)
        for u, v, cnt in edges:
            head = max(0, max_moves - dist[u])
            tail = max(0, max_moves - dist[v])
            reachable += min(cnt, head + tail)
        return reachable