C++ Dijkstra and DFS DP
First we run dijkstra from n to 1 so that we can find shortest distance from n to all nodes. Since, it is an undirected graph, the shortest distance is same for
First we run dijkstra from n to 1 so that we can find shortest distance from n to all nodes. Since, it is an undirected graph, the shortest distance is same for reverse path also. Then we do a DFS DP for findin the path according to the given constraints.\n\n```\nstruct fun\n{\n\tbool operator() (pair<int,int>& p1, pair<int,int>& p2)\n\t{\n\t\treturn p1.second>p2.second;\n\t}\n};\nvector<int> dijkstra(vector<vector<pair<int,int>>>& adj,int n)\n{\n\tvector<int> ret(n+1,INT_MAX);\n\tvector<int> grey(n+1);\n\tpriority_queue<pair<int,int>,vector<pair<int,int>>,fun> q;\n\tq.push({n,0});\n\tret[n]=0;\n\twhile(!q.empty())\n\t{\n\t\tpair<int,int> u=q.top();\n\t\tq.pop();\n\t\tif(grey[u.first])\n\t\t\tcontinue;\n\t\tret[u.first]=u.second;\n\t\tgrey[u.first]=1;\n\t\tfor(auto v:adj[u.first])\n\t\t\tif(ret[v.first]>u.second+v.second)\n\t\t\t\tq.push({v.first,u.second+v.second});\n\t}\n\treturn ret;\n}\n#define mod 1000000007\nint memo[20001];\nint dp(int u,vector<vector<pair<int,int>>>& adj,vector<int>& distance)\n{\n\tif(u==1)\n\t\treturn 1;\n\telse if(memo[u]!=-1)\n\t\treturn memo[u];\n\telse\n\t{\n\t\tlong q=0;\n\t\tfor(auto& v:adj[u])\n\t\t\tif(distance[v.first]>distance[u])\n\t\t\t\tq+=dp(v.first,adj,distance);\n\t\treturn memo[u]=q%mod;\n\t}\n}\nint countRestrictedPaths(int n, vector<vector<int>>& edges) \n{\n\tvector<vector<pair<int,int>>> adj(n+1);\n\tfor(auto x:edges)\n\t{\n\t\tadj[x[0]].push_back({x[1],x[2]});\n\t\tadj[x[1]].push_back({x[0],x[2]});\n\t}\n\tvector<int> temp=dijkstra(adj,n);\n\tmemset(memo,-1,sizeof(memo));\n\treturn dp(n,adj,temp);\n}\n```
['Dynamic Programming', 'C']