Simple Dijkstra and dfs with memoization(c++)
\n#define F first\n#define S second\nclass Solution {\npublic:\n     int dfs( vector<vector<pair<int,int>>> &adj, vector<int> &dis,int node,int pre_dis, vector<
```\n#define F first\n#define S second\nclass Solution {\npublic:\n     int dfs( vector<vector<pair<int,int>>> &adj, vector<int> &dis,int node,int pre_dis, vector<int> &dp)\n {\n     int mod = 1000000007;\n     if(node == adj.size()-1){\n        return 1;\n     }\n     if(pre_dis <= dis[node])return 0;\n     if(dp[node]!=-1)return dp[node];\n      int res = 0;\n     for(int i=0; i<adj[node].size(); i++)\n     {\n           res = ((res%mod) +  (dfs(adj, dis, adj[node][i].F, dis[node],dp)%mod))%mod;\n     }\n     return dp[node] = res;\n }\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n                vector<int> dis(n+1, INT_MAX);\n                vector<int> dp(n+1, -1);\n                dis[n] = 0;\n                vector<vector<pair<int,int>>> adj(n+1);\n                for(int i=0;i<edges.size();i++)\n                {\n                    int u = edges[i][0];\n                    int v = edges[i][1];\n                    int w = edges[i][2];\n                    adj[u].push_back({v,w});\n                    adj[v].push_back({u,w});\n                }\n\n                priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > pq;\n                pq.push({0,n});\n                while(!pq.empty())\n                {\n                         int curr = pq.top().F;\n                         int node = pq.top().S;\n                         pq.pop();\n                         for(int i = 0;i<adj[node].size();i++)\n                         {\n                                 /*if(vis[adj[node][i].F])continue;\n                                 vis[adj[node][i].F]=true*/\n                                 int w = adj[node][i].S;\n                                 if(curr + w <dis[adj[node][i].F])\n                                 {\n                                     dis[adj[node][i].F ] = curr + w;\n                                     pq.push({curr+w, adj[node][i].F});\n                                 }\n                         }\n\n                }\n                /*for(int i=1;i<=n;i++)cout<<dis[i]<<"  "; */\n                return dfs(adj, dis, 1, INT_MAX, dp); \n    }\n};\n```
[]