1
class Solution {
2
 public:
3
  int reachableNodes(vector<vector<int>> &edges, int maxMoves, int n) {
4
    const int INF = 1e8;
5
    vector < vector<pair<int, int>> g(n);
6
    for (auto i : edges) {
7
      g[i[0]].push_back({i[1], i[2]});
8
      g[i[1]].push_back({i[0], i[2]});
9
    }
10

11
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
12
    pq.push({0, 0}); // distance,node
13
    vector<int> d(n, INF);
14
    d[0] = 0;
15

16
    while (!pq.empty()) {
17
      int dist = pq.top().first;
18
      int node = pq.top().second;
19
      pq.pop();
20
      // if(d[u.second]!=u.first) continue;
21
      for (auto it : g[node]) {
22
        if (d[it.first] > dist + it.second + 1) // since number of edges=nodes in between+1
23
        {
24
          d[it.first] = dist + it.second + 1;
25
          pq.push({d[it.first], it.first});
26
        }
27
      }
28
    }
29
    // now we have minimum distances to reach each node, so check how many
30
    // reachable with minMoves
31
    int ans = 0;
32
    for (int i = 0; i < n; ++i) { // add 1 for nodes that can be visited
33
      if (d[i] <= maxMoves) ans++;
34
    }
35

36
    /*
37
    Now add for intermediate newly added nodes
38
    Eg. 0->1 and 10 in between
39

40
    Visitable from 0 -> maxMoves-(dist/moves already covered by 0 (from source))
41
    Visitable from 1 -> maxMoves-(dist/moves already covered by 1 (from source))
42

43
    To calculate Extra nodes I can visit we follow above
44
    */
45
    for (auto i : edges) {
46
      int src = i[0], dest = i[1], between = i[2];
47
      int x = max(0, (maxMoves - d[src]));  // nodes visited using edge e[0]->e[1]
48
      int y = max(0, (maxMoves - d[dest])); // nodes visited using edge e[1]->e[0]
49
      ans += min(between, x + y);           // minimum to avoid overlapping in counting
50
    }
51
    return ans;