Shortest Path + DFS || Djikstra + DFS + DP || C++ Clean Code
Idea here is to first calculate Path with Minimum Cost from source = n i.e last node. For this we will use Djikstra\'s Algo. \n\n Now, that we have created dist
Idea here is to first calculate Path with Minimum Cost from `source = n` i.e last node. For this we will use Djikstra\'s Algo. \n\n* Now, that we have created distance array, such that `dist[x] = distanceToLastNode(x)`\n* Then, we need to find paths from 1 to n, such that \n\n\t\t distanceToLastNode(node) > distanceToLastNode(adjacentNode)\n\t\t -> i.e in any restricted path, distance of adjacent node(neighbour) should be always less that current node distance to the destination node i.e n\n\t\t \n\t\tEx:   3  ----  4 , say an edge from 3 - 4 is there and dist[3] = 5 & dist[4] = 2. We are at node 3.\n\t\t\n\t\tSo, since dist[node] > dist[adjacent node] , thus we can that this edge is a restricted edge. \n\t\tAlso, we would exclude this node if condition does not hold true.\n\t\t\n* So, to get count of all restricted path we will simply do a DFS from `source = 1` to `destination = n`\n* And, for every node check if its adjacent node\'s distance is less that current node\'s distance. \n\t* If yes, then move ahead in that path.\n\t* Else, exclude this adjacent node from our path.\n* Since, we will have overlapping subproblems, using memoization (DP) will help from getting TLE xD.\n\t* dp[node] : number of restricted paths from 1 to node.\n* Base case will be when we reach destination, which means we have found one restricted path. So return 1.\n\n# Code: \n\n```\nclass Solution {\n    int mod = 1e9 + 7;\npublic:\n    \n    int restrictedPaths(vector<vector<pair<int, int>>>& adj, vector<int>& dist, vector<int>& dp, int node, const int& n) {\n        if(node == n) return 1;\n        \n        if(dp[node] != -1) return dp[node];\n        \n        int paths = 0;\n        \n        for(auto& it : adj[node]) {\n            if(dist[it.first] < dist[node]) {\n                paths = (paths + restrictedPaths(adj, dist, dp, it.first, n)) % mod;\n            }\n        }\n        \n        return dp[node] = paths;\n    }\n    \n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        \n        vector<vector<pair<int, int>>> adj(n+1);\n        \n        for(auto& edge : edges) {\n            adj[edge[0]].push_back({edge[1], edge[2]});\n            adj[edge[1]].push_back({edge[0], edge[2]});\n        }\n        \n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        vector<int> dist(n+1, INT_MAX);\n\n        int source = n, destination = 1;\n        \n            \n        dist[source] = 0;\n        pq.push({0, source});\n\n        while(pq.size()) {\n            int dis = pq.top().first;\n            int node = pq.top().second;\n            \n            pq.pop();\n\n            for(auto& it : adj[node]) {\n                int adjNode = it.first;\n                int wt = it.second;\n\n                if(dis + wt < dist[adjNode]) {\n                    dist[adjNode] = dis + wt;\n                    pq.push({dis + wt, adjNode});\n                }\n            }\n        }\n        \n        vector<int> dp(n+1, -1);\n        return restrictedPaths(adj, dist, dp, destination, n);\n    }\n};\n```\n\n***If you find this solution helpful do give it a like :)***
['Dynamic Programming', 'Depth-First Search', 'Graph', 'C', 'Shortest Path']