C++ | Explanation | Easy to understand
\tC++ Code  with explanation \n\t\n\t\n\tWe can use dijsktra Algorithm for finding the distance from src = lastNode to each node. \n\tBecause the constraints 0<
\tC++ Code  with explanation \n\t\n\t\n\tWe can use dijsktra Algorithm for finding the distance from src = lastNode to each node. \n\tBecause the constraints 0<=n<=2 * 10 ^4 so that dijsktra (n^2) won\'t be work for this we \n\tuse Min-Heap (in C++ standard template library (STL) we use Priority queue).\n\t\n\t\n\tAnd Then we can apply DFS for finding all paths which have the property (dist[i]>dist[i+1]) \n\tand 0<=i<=k-1.\n\twhere k is size of sequence from node 1 to node n.\n\n\n\n\tclass Solution {\n\t\t\t\tpublic:\n\t\t\t\t\tconst int mod = 1e9+7;\n\t\t\t\t\tint dp[20005];\n\t\t\t\t\tint dfs(int start,vector<pair<int,int>>adj[],int n,int dist[])\n\t\t\t\t\t{\n\t\t\t\t\t\tif(start==n)\n\t\t\t\t\t\t{\n\t\t\t\t\t\t\treturn 1;\n\t\t\t\t\t\t}\n\t\t\t\t\t\tif(dp[start]!=-1)\n\t\t\t\t\t\t{\n\t\t\t\t\t\t\treturn dp[start];\n\t\t\t\t\t\t}\n\t\t\t\t\t\tint ans = 0;\n\t\t\t\t\t\tfor(auto x:adj[start])\n\t\t\t\t\t\t{\n\n\t\t\t\t\t\t\tif(dist[start]>dist[x.first])\n\t\t\t\t\t\t\t{\n\t\t\t\t\t\t\t\tans = (ans + dfs(x.first,adj,n,dist))%mod;\n\t\t\t\t\t\t\t}\n\t\t\t\t\t\t}\n\t\t\t\t\t\treturn dp[start] = ans%mod;\n\t\t\t\t\t}\n\n\t\t\t\t\tint countRestrictedPaths(int n, vector<vector<int>>& edges) {\n\n\n\t\t\t\t\t\tint dist[n+1];\n\t\t\t\t\t\tmemset(dist,INT_MAX,sizeof(dist));\n\n\t\t\t\t\t\tmemset(dp,-1,sizeof(dp));\n\t\t\t\t\t\tvector<pair<int,int>>adj[n+1];\n\t\t\t\t\t\tfor(auto x:edges)\n\t\t\t\t\t\t{\n\t\t\t\t\t\t\tadj[x[0]].push_back({x[1],x[2]});   \n\t\t\t\t\t\t\tadj[x[1]].push_back({x[0],x[2]});\n\t\t\t\t\t\t}\n\t\t\t\t\t\tbool vis[n+1];\n\t\t\t\t\t\tmemset(vis,false,sizeof(vis));\n\t\t\t\t\t\tpriority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;\n\t\t\t\t\t\tdist[n] = 0;\n\t\t\t\t\t\tpq.push({0,n});\n\t\t\t\t\t\tfor(int i = 0;i<n;i++)\n\t\t\t\t\t\t{\n\t\t\t\t\t\t\tdist[i] = INT_MAX;\n\t\t\t\t\t\t}\n\t\t\t\t\t\twhile(!pq.empty())\n\t\t\t\t\t\t{\n\n\t\t\t\t\t\t\tauto cur = pq.top();\n\t\t\t\t\t\t\tpq.pop();\n\t\t\t\t\t\t\tint u = cur.second;\n\t\t\t\t\t\t\tvis[u] = true;\n\n\n\t\t\t\t\t\t\tfor(auto v:adj[u])\n\t\t\t\t\t\t\t{\n\n\t\t\t\t\t\t\t\tif(!vis[v.first]  and dist[u]!=INT_MAX and dist[u]+v.second < dist[v.first])\n\t\t\t\t\t\t\t\t{\n\t\t\t\t\t\t\t\t   dist[v.first]  = dist[u] + v.second;  \n\t\t\t\t\t\t\t\t\tpq.push({dist[v.first],v.first});\n\t\t\t\t\t\t\t\t}\n\n\t\t\t\t\t\t\t}\n\t\t\t\t\t\t}\n\t\t\t\t\t\treturn dfs(1,adj,n,dist);\n\n\t\t\t\t\t}\n\t\t\t\t};
[]