C++ || DIJKSTRA || DFS + MEMOIZATION || MOST EASY || NEAT || CODE ✅
\n#define ll long long\n\nclass Solution {\npublic:\n    \n    int mod = 1e9+7;\n   \n    \n    // step1> Reverse Dijkstra\n    // step2> dfs + memo\n    \n    
```\n#define ll long long\n\nclass Solution {\npublic:\n    \n    int mod = 1e9+7;\n   \n    \n    // step1> Reverse Dijkstra\n    // step2> dfs + memo\n    \n    int n;\n    vector < vector < pair <int,ll> > > adj;\n    \n    \n //-------STEP 1: Find the minimum distance from all nodes to node \'n\' using Dijkstra--------\n    vector<ll> dijkstra(int src){\n    \n        vector<ll> dist(n, LLONG_MAX);\n        dist[src] = 0;\n        \n        priority_queue < pair<ll,int> , vector < pair<ll,int> > , greater < pair<ll,int> > > minheap; // <dist,node>\n        minheap.push({0,src});\n        \n        while(minheap.size()){\n            \n            auto [currDist , currNode] = minheap.top();\n            minheap.pop();\n            \n            for(auto [adjNode, weight] : adj[currNode]){\n                if(currDist + weight < dist[adjNode]){\n                    dist[adjNode] = currDist + weight;\n                    minheap.push({dist[adjNode], adjNode});\n                }\n            }\n        }\n        \n        return dist; \n        \n    }\n//----------END of Step 1 ------------------------------------------------\n\t\n\t\n\t\n// \t------Step 2: Start DFS from node \'1\' and memoize the results. -------------\n\n/*Always move to next node if min distance of next node to \'n\' \nis LESS than min distance of current node to \'n\'*/\n\nint allValidPathsFrom(int currNode, vector<ll>& distanceToLastFrom, vector<int>& totValidPathsFrom){\n\n\tif(totValidPathsFrom[currNode]!=-1) return totValidPathsFrom[currNode]%mod;\n\n\tif(currNode == n-1)\n\t\treturn totValidPathsFrom[currNode] = 1;\n\n\tint totPaths = 0;\n\n\tfor(auto [adjNode, weight] : adj[currNode]){\n\t\tif(distanceToLastFrom[adjNode] < distanceToLastFrom[currNode])\n\t\t\ttotPaths = ( totPaths%mod + allValidPathsFrom(adjNode,distanceToLastFrom,totValidPathsFrom)%mod )%mod;\n\t}\n\n\treturn totValidPathsFrom[currNode] = totPaths%mod; \n\n\n}\n\n//-------END of Step 2----------------------------------\n\n    \n// ----- driver-------------------------------------------\t\nint countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        this->n = n;\n        adj.resize(n);\n        \n        for(auto& e : edges){\n            int u = e[0]-1;\n            int v = e[1]-1;\n            ll w = e[2];\n            \n            adj[u].push_back({v,w});\n            adj[v].push_back({u,w});\n        }\n        \n        //1. Reverse disjkastra\n        int src = n-1;\n        vector<ll> distanceToLastFrom = dijkstra(src);\n        \n        \n        //2. Dfs with memoization to get ans\n        vector<int> totValidPathsFrom(n,-1); // the memoization array\n        return allValidPathsFrom(0, distanceToLastFrom,totValidPathsFrom );\n        \n        \n    }\n};\n```
[]