<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>

#include <bits/stdc++.h>
using namespace std;
#define read(type) readInt<type>() // Fast read
// #define int long long
#define nL "\n"

#define vi vector<int>
#define aint(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set
#define MOD 1000000007
#define imax INT_MAX
#define imin INT_MIN
#define exp 1e9
#define sz(x) (int((x).size()))
#define pq_max priority_queue<int>
#define pq_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)

/* FUNCTIONS */
#define f(i, s, e) for (int i = s; i <= e; i++)
#define rf(i, e, s) for (int i = e; i >= s; i--)




class Solution
{
public:
    int reachableNodes(vector<vector<int>> &edges, int maxMoves, int n)
    {
        int m = edges.size();
        vi dist(n, imax);
        // q.push({0, 0});
        vector<vector<array<int, 2>>> graph(n);
        for (auto x : edges)
        {
            graph[x[0]].push_back({x[1], x[2]});
            graph[x[1]].push_back({x[0], x[2]});
        }
        // cout << "graph: " << nL;
        // f(i, 0, n - 1)
        // {
        //     cout << i << ": ";
        //     for (auto x : graph[i])
        //         cout << x[0] << " ";
        //     cout << nL;
        // }
        // return 0;
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> q; //{dist, node}
        dist[0] = 0;
        q.push({0, 0});

        while (!q.empty())
        {
            auto it = q.top();
            int d = it[0];
            int u = it[1];
            q.pop();
            if (d > dist[u])
                continue;
            for (auto x : graph[u])
            {
                int v = x[0];
                int w = x[1];
                if (dist[u] + w + 1 < dist[v])
                {
                    dist[v] = dist[u] + w + 1;
                    q.push({dist[v], v});
                }
            }
        }

        // print_v(dist);
        // cout << nL;
        int ans = 0;
        f(i, 0, m - 1)
        {
            int u = edges[i][0];
            int v = edges[i][1];
            int cnt = edges[i][2];
            if (dist[u] <= maxMoves)
            {
                // ans++;
                int extra = min(maxMoves - dist[u], cnt);
                ans += extra;
                cnt -= extra;
            }
            if (dist[v] <= maxMoves)
            {
                // ans++;
                int extra = min(maxMoves - dist[v], cnt);
                ans += extra;
            }
        }

        f(i, 0, n - 1)
        {
            if (dist[i] <= maxMoves)
                ans++;
        }

        return ans;
    }
};
52294