[C++] || Dijkstra Algorithm || DP
Intuition\n Describe your first thoughts on how to solve this problem. \nThe minimum cost can be found using Dijkstra Algorithm and we can use DP array to store
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe minimum cost can be found using Dijkstra Algorithm and we can use DP array to store the count value.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n-> Use Dijkstra to find the shortest amount of time.\n-> Use DP to keep states of shortest time fo a node (the count array)\n-> while finding shortest time\n-> when we find a shorter time we change dp by new value by the dp value of its parent (from where its coming from).\n-> when we find equal time we add value to current node\'s dp, i.e, adding the dp values of its parent or the adjacent where its coming from.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(E*log(N))\nE --> number of edges\nN --> number of vertices or nodes\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<vector<pair<int, int>>> adj(n);\n        for(auto it : roads)\n        {\n            int from = it[0];\n            int to = it[1];\n            int time = it[2];\n            adj[from].push_back({to, time});\n            adj[to].push_back({from, time});\n        }\n        long long mod = 1e9 + 7;\n        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;\n        pq.push({0, 0});\n        vector<long long> dist(n, 1e15);\n        vector<long long> count(n, 0);\n        dist[0] = 0;\n        count[0] = 1;\n        while(pq.size())\n        {\n            long long timetaken = pq.top().first;\n            int curr = pq.top().second;\n            pq.pop();\n            for(auto it : adj[curr])\n            {\n                int neigh = it.first;\n                int traveltime = it.second;\n                if(dist[neigh] == timetaken + traveltime)\n                {\n                    count[neigh] = (count[neigh] + count[curr]) % mod;\n                }\n                else if(dist[neigh] > timetaken + traveltime)\n                {\n                    dist[neigh] = timetaken + traveltime;\n                    pq.push({dist[neigh], neigh});\n                    count[neigh] = count[curr];\n                }\n            }\n        }\n        return count[n-1] % mod;\n    }\n};\n```
['Dynamic Programming', 'Graph', 'C++']