LeetCode Solutions

			

class Solution {
 public:
  int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
    using P = pair<int, int>;
    vector<vector<P>> graph(n);
    priority_queue<P, vector<P>, greater<>> minHeap;  // (d, u)
    vector<int> dist(n, maxMoves + 1);

    for (const vector<int>& e : edges) {
      const int u = e[0];
      const int v = e[1];
      const int cnt = e[2];
      graph[u].emplace_back(v, cnt);
      graph[v].emplace_back(u, cnt);
    }

    minHeap.emplace(0, 0);
    dist[0] = 0;

    while (!minHeap.empty()) {
      const auto [d, u] = minHeap.top();
      minHeap.pop();
      // Already takes maxMoves to reach u, can't explore anymore
      if (dist[u] >= maxMoves)
        break;
      for (const auto& [v, w] : graph[u]) {
        const int newDist = d + w + 1;
        if (newDist < dist[v]) {
          dist[v] = newDist;
          minHeap.emplace(newDist, v);
        }
      }
    }

    const int reachableNodes =
        count_if(begin(dist), end(dist), [&](int d) { return d <= maxMoves; });
    int reachableSubnodes = 0;

    for (const vector<int>& e : edges) {
      const int u = e[0];
      const int v = e[1];
      const int cnt = e[2];
      // Reachable nodes of e from u
      const int a = dist[u] > maxMoves ? 0 : min(maxMoves - dist[u], cnt);
      // Reachable nodes of e from v
      const int b = dist[v] > maxMoves ? 0 : min(maxMoves - dist[v], cnt);
      reachableSubnodes += min(a + b, cnt);
    }

    return reachableNodes + reachableSubnodes;
  }
};

			

class Solution {
  public int reachableNodes(int[][] edges, int maxMoves, int n) {
    List<Pair<Integer, Integer>>[] graph = new List[n];
    Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // (d, u)
    int[] dist = new int[n];
    Arrays.fill(dist, maxMoves + 1);

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] e : edges) {
      final int u = e[0];
      final int v = e[1];
      final int cnt = e[2];
      graph[u].add(new Pair<>(v, cnt));
      graph[v].add(new Pair<>(u, cnt));
    }

    minHeap.offer(new int[] {0, 0});
    dist[0] = 0;

    while (!minHeap.isEmpty()) {
      final int d = minHeap.peek()[0];
      final int u = minHeap.poll()[1];
      // Already takes maxMoves to reach u, can't explore anymore
      if (d >= maxMoves)
        break;
      for (Pair<Integer, Integer> node : graph[u]) {
        final int v = node.getKey();
        final int w = node.getValue();
        final int newDist = d + w + 1;
        if (newDist < dist[v]) {
          dist[v] = newDist;
          minHeap.offer(new int[] {newDist, v});
        }
      }
    }

    final int reachableNodes = (int) Arrays.stream(dist).filter(d -> d <= maxMoves).count();
    int reachableSubnodes = 0;

    for (int[] e : edges) {
      final int u = e[0];
      final int v = e[1];
      final int cnt = e[2];
      // Reachable nodes of e from u
      final int a = dist[u] > maxMoves ? 0 : Math.min(maxMoves - dist[u], cnt);
      // Reachable nodes of e from v
      final int b = dist[v] > maxMoves ? 0 : Math.min(maxMoves - dist[v], cnt);
      reachableSubnodes += Math.min(a + b, cnt);
    }

    return reachableNodes + reachableSubnodes;
  }
}

			

class Solution:
  def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
    graph = [[] for _ in range(n)]
    minHeap = [(0, 0)]  # (d, u)
    dist = [maxMoves + 1] * n
    dist[0] = 0

    for u, v, cnt in edges:
      graph[u].append((v, cnt))
      graph[v].append((u, cnt))

    while minHeap:
      d, u = heapq.heappop(minHeap)
      # Already takes maxMoves to reach u, can't explore anymore
      if dist[u] >= maxMoves:
        break
      for v, w in graph[u]:
        newDist = d + w + 1
        if newDist < dist[v]:
          dist[v] = newDist
          heapq.heappush(minHeap, (newDist, v))

    reachableNodes = sum(d <= maxMoves for d in dist)
    reachableSubnodes = 0

    for u, v, cnt in edges:
      # Reachable nodes of e from u
      a = 0 if dist[u] > maxMoves else min(maxMoves - dist[u], cnt)
      # Reachable nodes of e from v
      b = 0 if dist[v] > maxMoves else min(maxMoves - dist[v], cnt)
      reachableSubnodes += min(a + b, cnt)

    return reachableNodes + reachableSubnodes