<p>You are given an undirected graph (the <strong>&quot;original graph&quot;</strong>) with <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>. You decide to <strong>subdivide</strong> each edge in the graph into a chain of nodes, with the number of new nodes varying between each edge.</p>

<p>The graph is given as a 2D array of <code>edges</code> where <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>, cnt<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> in the original graph, and <code>cnt<sub>i</sub></code> is the total number of new nodes that you will <strong>subdivide</strong> the edge into. Note that <code>cnt<sub>i</sub> == 0</code> means you will not subdivide the edge.</p>

<p>To <strong>subdivide</strong> the edge <code>[u<sub>i</sub>, v<sub>i</sub>]</code>, replace it with <code>(cnt<sub>i</sub> + 1)</code> new edges and <code>cnt<sub>i</sub></code> new nodes. The new nodes are <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>, ..., <code>x<sub>cnt<sub>i</sub></sub></code>, and the new edges are <code>[u<sub>i</sub>, x<sub>1</sub>]</code>, <code>[x<sub>1</sub>, x<sub>2</sub>]</code>, <code>[x<sub>2</sub>, x<sub>3</sub>]</code>, ..., <code>[x<sub>cnt<sub>i</sub>-1</sub>, x<sub>cnt<sub>i</sub></sub>]</code>, <code>[x<sub>cnt<sub>i</sub></sub>, v<sub>i</sub>]</code>.</p>

<p>In this <strong>new graph</strong>, you want to know how many nodes are <strong>reachable</strong> from the node <code>0</code>, where a node is <strong>reachable</strong> if the distance is <code>maxMoves</code> or less.</p>

<p>Given the original graph and <code>maxMoves</code>, return <em>the number of nodes that are <strong>reachable</strong> from node </em><code>0</code><em> in the new graph</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/01/origfinal.png" style="width: 600px; height: 247px;" />
<pre>
<strong>Input:</strong> edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
<strong>Output:</strong> 13
<strong>Explanation:</strong> The edge subdivisions are shown in the image above.
The nodes that are reachable are highlighted in yellow.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
<strong>Output:</strong> 23
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= edges.length &lt;= min(n * (n - 1) / 2, 10<sup>4</sup>)</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= u<sub>i</sub> &lt; v<sub>i</sub> &lt; n</code></li>
	<li>There are <strong>no multiple edges</strong> in the graph.</li>
	<li><code>0 &lt;= cnt<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= maxMoves &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= n &lt;= 3000</code></li>
</ul>

// class Solution {
// public:
//     int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
//          vector<pair<int,int>>gr[n];
//         priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
//         vector<int> distance(n, INT_MAX);
//          distance[0]=0;
//          for(auto t:edges){
//             int u=t[0];
//             int v=t[1];
//             int dis=t[2]+1;
//             gr[u].push_back({dis,v});
//             gr[v].push_back({dis,u});

//          }
//          pq.push({0,0});
//          int ans=0;
//          while(!pq.empty()){
//                auto t=pq.top();
//                pq.pop();
//                int node=t.second;
//                int dis=t.first;
//                for(auto r:gr[node]){
//                   int newnode=r.second;
//                   int add_dis=r.first;
//                   if(add_dis+dis>maxMoves){ // exceed maxMoves 
//                     ans+=(add_dis+dis-maxMoves-1);
//                     continue;
//                  }
//                  if(distance[newnode]>add_dis+dis){  // agar min dis hai to add
//                     distance[newnode]=add_dis+dis;
//                     pq.push({add_dis+dis,newnode});
//                     continue;
//                  }else if (distance[newnode]==add_dis+dis){
//                     ans+=add_dis+dis;  // counting here only as extra
//                     pq.push({add_dis+dis,newnode});
//                     continue;

//                  }
//                 //  ans+=add_dis;  // count adding 
//          }
//         }
//          for(auto t:distance){
//             if(t!=INT_MAX)ans=ans+1+t;
//          }
//          return ans+1;
//     }
// };

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<pair<int,int>> gr[n];
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        vector<int> distance(n, INT_MAX);
        distance[0] = 0; 
        for (auto& t : edges) {
            int u = t[0];
            int v = t[1];
            int dis = t[2] + 1;  // Add 1 because each edge has t[2] nodes in between
            gr[u].push_back({dis, v});
            gr[v].push_back({dis, u});
        }
        pq.push({0, 0}); // distance of each node from 0 
        while (!pq.empty()) {
            auto t = pq.top();
            pq.pop();
            int node = t.second;
            int dis = t.first;
            if (dis > distance[node]) continue;   // cycle prevent
            for (auto& r : gr[node]) {
                int newNode = r.second;
                int addDis = r.first;
                if (distance[newNode] > dis + addDis && dis + addDis <= maxMoves) {
                    distance[newNode] = dis + addDis;
                    pq.push({dis + addDis, newNode});
                }
            }
        }

        int ans = 0;
        // Count all reachable nodes
        for (int i = 0; i < n; i++) {
            if (distance[i] !=INT_MAX) ans++;    // real nodes calculated
        }
        
        // Count the extra nodes that can be reached within the edge subdivisions
        // between node calculations
        for (auto& t : edges) {
            int u = t[0];
            int v = t[1];
            int dis = t[2]; // node in between
            int reachU = (distance[u] <=maxMoves) ? maxMoves - distance[u] : 0;   // between m kitne from both end
            int reachV = (distance[v] <=maxMoves) ? maxMoves - distance[v] : 0;
            ans += min(dis, reachU + reachV);
        }
        
        return ans;
    }
};

46515