Dijkstra + Top Down DP C++ ✌️
Intuition\nApplying dijkstra to find shortest distance then using a dfs to find number of paths having this shortest distance.\n\n\n# Approach\nFirst apply dijk
# Intuition\nApplying dijkstra to find shortest distance then using a dfs to find number of paths having this shortest distance.\n\n\n# Approach\nFirst apply dijkstra from n-1 node then use the distance array generated in a dfs function which is memoized for optimization.\n\n\n# Complexity\n- Time complexity: O(ElogV) (Dijkstra) +O(V) DFS(memoized)\n\n\n- Space complexity:\nO(V)\n\n# Code\n```\nclass Solution {\n\n   long long int shortest_distance;\n    int mod=1e9+7;\n\n    public:\n\n    int dp[202];\n\n    int dfs(vector<pair<int,int>> adj[],int node,vector<long long int>& dist)\n    {\n       if(node==dist.size()-1)return 1;\n\n       if(dp[node]!=-1)return dp[node];\n\n        long long  int distance_to_dest=dist[node];\n\n       int total=0;\n\n       for(auto [nd,wt]:adj[node])\n       {\n           if(0LL+wt+dist[nd]==distance_to_dest)// the path must be shortest one \n           {\n               total=(0LL+total+dfs(adj,nd,dist))%mod;// counting all paths\n           }\n       }\n\n       return dp[node]=total;\n\n    }\n    \n    int countPaths(int n, vector<vector<int>>& roads) {\n\n        memset(dp,-1,sizeof(dp));\n        \n        vector<pair<int,int>> adj[n];\n        \n        for(auto a:roads)\n        {\n            adj[a[0]].push_back({a[1],a[2]});\n            adj[a[1]].push_back({a[0],a[2]});   \n        }\n        \n        priority_queue< pair<long long int,int>,vector<pair<long long int,int>>,greater<pair<long long int,int>> > heap;\n        \n        vector<long long int> dist(n,LLONG_MAX);\n        \n        dist[n-1]=0;// dijkstra from reverse direction to find distan from node i to n-1 in O(1) during Dfs\n        \n        heap.push({0,n-1});\n        \n        while(heap.size())\n        {\n           auto [distance,node]=heap.top();\n          \n            heap.pop();\n\n           if(distance>dist[node])continue;\n\n           for(auto& [nd,wt]:adj[node])\n            {\n              long long  int summer=(0LL+wt+distance);\n            \n                if(dist[nd]>summer)\n                {      \n                    dist[nd]=summer;\n                    \n                    heap.push({dist[nd],nd});\n                }\n                \n            }\n        }\n\n        shortest_distance=dist[0];\n        \n        return dfs(adj,0,dist); \n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Graph', 'Shortest Path', 'C++']