[C++] Detailed Explanation | Easy Approach | DFS
Question Explanation:\nConsider ntoxSD[x] as the shortest distance of a path between node n and node x.\nFind the number of paths from node 1 that leads to node
**Question Explanation:**\nConsider ```ntoxSD[x]``` as the shortest distance of a path between ```node n``` and ```node x```.\nFind the number of paths from ```node 1``` that leads to ```node n``` such that all the nodes you come across while traversing that path has ```ntoxSD[node]``` in decreasing order.\n\n\n**Solution Approach:**\nStep 1: Make adjacency list.\nStep 2: Find shortest distance from the ```node n``` to all the nodes (using Dijkstra\'s Algorithm)\nStep 3: Do DFS from ```node 1``` and considering the path that leads to the ```node n``` follows the given condition (using memoization)\n\n\n**Code:**\n```\nclass Solution {\npublic:\n    int MOD=1e9+7;\n\t\n\t\n\t// Step 3.\n    // to calculate the required output using dfs and memoization\n    // storing the number of paths from a node (index of mem) that leads to the nth node with ntoxSD in decreasing order in vector mem\n    int computeRequiredAnswer(int cnode, int n, vector<int> &mem, vector<int> &dist, int &ans, vector<vector<pair<int, int>>> &graph) {\n\t\t// if we have reached the node n\n        if(cnode==n-1)\n            return 1;\n        \n\t\t// if we have already computed for the current node\n        if(mem[cnode]!=-1)\n            return mem[cnode];\n        \n\t\t// to compute mem[current node]\n        int cval=0;\n        for(auto a : graph[cnode]) {\n            if(dist[a.first]<dist[cnode]) {\n                cval=(cval+computeRequiredAnswer(a.first, n, mem, dist, ans, graph))%MOD;\n            }\n        }\n        mem[cnode]=cval;\n        return cval;\n    }\n    \n\t\n\t// Step 2.\n    // to calculate shortest distance of all the nodes from nth node\n    vector<int> computeShortestPath(int n, vector<vector<pair<int, int>>> &graph) {\n        vector<int> dist(n, INT_MAX);\n        dist[n-1]=0;\n        \n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        pq.push({0, n-1});\n        \n\t\t//Dijkstra\'s Algorithm\n        while(!pq.empty()) {\n            int cnode=pq.top().second;\n            int cdist=pq.top().first;\n            pq.pop();\n            for(auto a : graph[cnode]) {\n                if(dist[a.first] > cdist+a.second) {\n                    dist[a.first]=cdist+a.second;\n                    pq.push({dist[a.first], a.first});\n                }\n            }\n        }\n        return dist;\n    }\n    \n\t\n\t// Step 1.\n    // main function\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<vector<pair<int, int>>> graph(n);\n        for(auto e : edges) {\n            graph[e[0]-1].push_back({e[1]-1, e[2]});\n            graph[e[1]-1].push_back({e[0]-1, e[2]});\n        }\n        \n\t\t// to store the required shortest path\n        vector<int> dist;\n        dist=computeShortestPath(n, graph);\n\t\t\n\t\t// to store the number of paths that follows the given condition for each node\n        vector<int> mem(n, -1);\n        int ans=computeRequiredAnswer(0, n, mem, dist, ans, graph);\n\t\t\n        return ans;\n    }\n};\n```\n*Please upvote if you find this helpful*
['Depth-First Search', 'Memoization', 'C']