C++ - Dijkstra algorithm || Easy Understanding
Apply Dijkstra shortest path algorithm as the problem involves shortest distance from source to destination. We need to modify Dijkstra\'s algorithm so that it 
Apply **Dijkstra shortest path algorithm** as the problem involves shortest distance from source to destination. We need to modify **Dijkstra\'s algorithm** so that it can keep track of the path counts from node 0 to every other node in a way that it can keep track of the distance from every other node to node 0 with the shortest possible distance as the ultimate goal of the problem.\n\n* If you find a shortest distance then update the path with new value.\n* If you find a equal shortest distance then add the value of the parrent node path number to the current node.\n\n\n**P.S**: Use **`long long`** properly.\n\n\n**Time Complexity**: **```O(E * logV + N)```**, where **E** is number of roads, **V** is number of nodes.\n**Space Complexity**: **```O(E + V)```**\n\n**C++ code:**\n```\n\nclass Solution {    \nprivate:\n    int dijkstra(vector<pair<int, int>> adj[], int n) {\n\t\tint mod = 1e9 + 7;\n        // priority queue for keep track of min distance \n        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;\n        // store the distance and number of paths\n        vector<long long> dis(n, 1e15), path(n, 0);\n\n        // push the initial node and distance to reach start is 0\n        pq.push({0, 0});\n        // mark the distance to 0\n        dis[0] = 0;\n        // mark the path number to 1\n        path[0] = 1;\n\n        // until queue is not empty\n        while (!pq.empty()) {\n            // get the top (min distance) element from priority queue and remove\n            long long dist = pq.top().first;\n            int node = pq.top().second;\n            pq.pop();\n\n            // iterate on its adjacent nodes\n            for (auto &child : adj[node]) {\n                int adjNode = child.first;\n                long long wt = child.second;\n\n                // if it min distance to reach at a node then update it\n                if (dist + wt < dis[adjNode]) {\n                    dis[adjNode] = dist + wt;\n                    path[adjNode] = path[node];\n                    pq.push({dist + wt, adjNode});\n                }\n                else if (dist + wt == dis[adjNode]) {\n                    //if it already visited with the shortest dis then increse the path with the current node path\n                    path[adjNode] = (path[node] + path[adjNode]) % mod;\n                }\n            }\n        }\n\n        return path[n - 1];\n    }\n    \npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        // adjacency list\n        vector<pair<int, int>> adj[n];\n\n        // create the graph\n        for (auto &v : roads) {\n            adj[v[0]].push_back({v[1], v[2]});\n            adj[v[1]].push_back({v[0], v[2]});\n        }\n        \n        return dijkstra(adj, n);\n    }\n};\n\n```\n\nPlease **upvote** if you find this helpful. **:)**\nFeel free to comment in case of any doubt.
['Graph', 'C', 'C++']