Dijkstra's Algo using Priority queue || C++ Solution
\n# Complexity\n- Time complexity: O(E logV)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(V) + O(N)\n Add your space complexity here, e.
\n# Complexity\n- Time complexity: **O(E logV)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(V) + O(N)**\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>>& a) {\n        vector<pair<long long, long long>> adj[n];\n        // it -> from to weight\n        for(auto it:a){\n            adj[it[0]].push_back({it[1], it[2]});\n            adj[it[1]].push_back({it[0], it[2]});\n        }\n        vector<long long> ways(n, 0);\n        vector<long long> dist(n, LONG_MAX);\n        priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq; // dist node\n        pq.push({0, 0});\n        dist[0] = 0;\n        ways[0] = 1;\n        while(!pq.empty()){\n            long long d = pq.top().first;\n            long long node = pq.top().second;\n            pq.pop();\n            for(auto it:adj[node]){\n                long long wt = it.second;\n                long long adjnode = it.first;\n                if(d + wt < dist[adjnode]){\n                    dist[adjnode] = d + wt;\n                    ways[adjnode] = ways[node];\n                    pq.push({ dist[adjnode], adjnode});\n                }\n                else if(d + wt == dist[adjnode])\n                         ways[adjnode]=((ways[adjnode] % 1000000007 + ways[node]) % 1000000007) % 1000000007;\n            }\n        }\n        return ways[n - 1] % 1000000007;\n    }\n};\n```
['Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'C++']