<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:
    vector<vector<pair<int,int>>> adj;
    // vector<int> edges;
    // map<vector<int>,int> edge_index;
    map<vector<int>,int> edge_vis;

    vector<int> vis;
    void dfs(int nod,int costt,int maxMoves){
        // vis[node]=cost;
        // for(auto x: adj[node]){
        //     if(cost+x.second<=maxMoves && vis[x.first]>cost+x.second){
        //         dfs(x.first,cost+x.second,maxMoves);
        //         // edges[edge_index[{min(node,x.first),max(node,x.first),x.second}]]=1;
        //         edge_vis[{min(node,x.first),max(node,x.first)}]=1;
        //     }
        // }
        vis[nod]=costt;
        set<pair<int,int>> st;
        st.insert({costt,nod});
        while(!st.empty()){
            auto p=*st.begin();
            st.erase(p);
            int node=p.second;
            int cost=p.first;
            // for(auto x: adj[node]) cout<<x.first<<" "<<x.second<<endl;
            // vis[node]=cost;
            for(auto x: adj[node]){
                if(cost+x.second<=maxMoves && vis[x.first]>cost+x.second){
                    st.erase({vis[x.first],x.first});
                    vis[x.first]=cost+x.second;
                    st.insert({cost+x.second,x.first});
                    edge_vis[{min(node,x.first),max(node,x.first)}]=1;
                }
            }
        }



    }
    int reachableNodes(vector<vector<int>>& edgess, int maxMoves, int n) {
        adj.resize(n);
        for(int i=0;i<edgess.size();i++){
            vector<int> edge=edgess[i];
            adj[edge[0]].push_back({edge[1],edge[2]+1});
            adj[edge[1]].push_back({edge[0],edge[2]+1});
            edge_vis[{min(edge[0],edge[1]),max(edge[0],edge[1])}]=0;

        }
        // for(int i=0;i<n;i++){
        //     for(auto x: adj[i]) cout<<x.first<<" "<<x.second<<endl;
        // }


        // vis.resize(edgess.size());
        vis.resize(n,maxMoves+1);

        dfs(0,0,maxMoves);

        // for(int i=0;i<edgess.size();i++) cout<<edge_vis[{min(edgess[i][0],edgess[i][1]),max(edgess[i][0],edgess[i][1])}]<<endl;
        // for(int i=0;i<n;i++) cout<<vis[i]<<endl;
        // now we have to see how many unvisited nodes can be partially visited and to what extent 
        map<vector<int>,int> mp;
        for(int i=0;i<n;i++)
        {
            if(vis[i]<=maxMoves){
            for(auto x: adj[i]){
                if(!edge_vis[{min(x.first,i),max({x.first,i})}]){
                    mp[{min(i,x.first),max(i,x.first)}]+=maxMoves-vis[i];
                }
            }}
        }
        int ans=0;
        for(auto edge: edgess){
            vector<int> p ={min(edge[0],edge[1]),max(edge[0],edge[1])};
            // cout<<p[0]<<" "<<p[1]<<" "<<mp[p]<<endl;
            if(!edge_vis[p]){
                int maxi=edge[2];
                ans+=min(maxi,mp[p]);
            }
            else {
                // cout<<"HELLO"<<endl;
                ans+=edge[2];
            }
            // cout<<ans<<endl;
        }
        // return ans;
        for(int i=0;i<n;i++)
        {
            if(vis[i]<=maxMoves) ans++;
        }
        return ans;


        return 0;

        
    }
};
90819