beats 99% c++ explaination
Approach\n Describe your approach to solving the problem. \nthere are multiple seperate steps to reach to the final answer\n\n1)form the adj list\n\n2)find the 
# Approach\n<!-- Describe your approach to solving the problem. -->\nthere are multiple seperate steps to reach to the final answer\n\n1)form the adj list\n\n2)find the dist of every node from last node. to do this we can use [Dijkstra\u2019s Algorithm](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/) here we have implemented using a heap, we can also use sets.\nwe save all the distances in a vector called dist\n\n3)we now perform DFS from the first node \nin the dfs-> we go to all adj nodes and if dist from adj node is lesser then we call dfs function from that node too and when we reach node N then we return 1\nbut since this will take a lot of time we can make a dp to remember number of ways to reach end from each node this will make the code faster \n\n\n# Code\n```\nclass Solution {\n    vector<int>dist;\n    int node;\n    int MOD=1e9+7;\n    vector<int>dp;\n    int dfs(int i,vector<pair<int,int>>adj[])\n    {\n        if(i==node)\n            return 1;\n        if(dp[i]!=-1)\n            return dp[i];\n        int ans=0;\n        for(const auto & [a,b]:adj[i])\n            if(dist[i]>dist[a])\n            {\n                ans+=dfs(a,adj);\n                ans%=MOD;\n            }\n\n        return dp[i]=ans;\n    }\n\npublic:\n    // this makes the code run faster but is not needed for the code to function\n    Solution()\n    {\n        ios_base::sync_with_stdio(0);\n        cin.tie(0);\n    }\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        node=n;\n        vector<pair<int,int>>adj[n+1];\n        dp.resize(n+1,-1);\n        for(const auto & i:edges)\n        {\n            adj[i[0]].push_back({i[1],i[2]});\n            adj[i[1]].push_back({i[0],i[2]});\n        }\n\n        dist.resize(n+1,INT_MAX);\n        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;\n        q.push({0,n});\n\n        while(!q.empty())\n        {\n            const auto [a,b]=q.top();\n            q.pop();\n            if(dist[b]!=INT_MAX)\n                continue;\n            dist[b]=a;\n            for(const auto & [i,j]:adj[b])\n                if(dist[i]==INT_MAX)\n                    q.push({a+j,i});\n            \n        }\n        \n        return dfs(1,adj);\n        \n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Graph', 'Heap (Priority Queue)', 'C++']