Easy To Understand C++ Solution || Dijkstra
Intuition\nUse Dijkstra Algorithm to find the shortest distance between source node and destination node.Mean while maintain a seperate array/vector which takes
# Intuition\nUse Dijkstra Algorithm to find the shortest distance between source node and destination node.Mean while maintain a seperate array/vector which takes a note of number of shortest path to that particular node.\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nExcept for maintaining the seperate array/vector for number of shortest ways every thing is similar as Dijkstra\'s shortest path algo.\n**\nSo, For maintaining the seperate array/vector for number of shortest ways follow below instructions**:\n1).If the no of shortest paths for particulr node is empty or we are going to add for the first time directly add the number of shortest path from the parent node.\n**ways[adjNode]=ways[node]**\n2).And if already there is already entry for shortest path for particualr node then add the number of shortest path from parent and the current number of the shortest path of the node.\n** ways[adjNode]=(ways[adjNode]+ways[node])**\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(ElogV)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<pair<int,int>>adj[n];\n        for(int i=0;i<roads.size();i++)\n        {\n            adj[roads[i][0]].push_back({roads[i][1],roads[i][2]});\n            adj[roads[i][1]].push_back({roads[i][0],roads[i][2]});\n        }\n        vector<long long>distance(n,1e15);\n        vector<int>ways(n,0);\n\n        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;\n\n        ways[0]=1;\n        distance[0]=0;\n        pq.push({0,0});\n\n        while(!pq.empty())\n        {\n            int node=pq.top().second;\n            long long dis=pq.top().first;\n            pq.pop();\n            for(auto it:adj[node])\n            {\n                int adjNode=it.first;\n                long long edgeWght=it.second;\n\n                //New Entry\n                if(dis+edgeWght<distance[adjNode])\n                {\n                    ways[adjNode]=ways[node];\n                    distance[adjNode]=dis+edgeWght;\n                    pq.push({dis+edgeWght,adjNode});\n\n                }\n                else if(dis+edgeWght==distance[adjNode])\n                {\n                    ways[adjNode]=(ways[adjNode]+ways[node])%((int)1e9+7);\n                }\n            }\n        }\n        return ways[n-1]%((int)1e9+7);\n\n        \n    }\n};\n```
['Breadth-First Search', 'Graph', 'C++']