Best C++ Solution
Approach\nDijkstra\'s Algorithm\n\n# Complexity\n- Time complexity:\nO(ElogV)\n\n- Space complexity:\nO(V + E)\n\n# Code\n\nclass Solution {\npublic:\n    int c
# Approach\nDijkstra\'s Algorithm\n\n# Complexity\n- Time complexity:\n$$O(ElogV)$$\n\n- Space complexity:\n$$O(V + E)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector <pair<long long, long long>> adj[n];\n        for (auto it : roads) {\n            adj[it[0]].push_back({it[1], it[2]});\n            adj[it[1]].push_back({it[0], it[2]});\n        }\n        priority_queue <pair<long long, long long>, vector<pair<long long, long long>>, greater<>> pq;\n        vector <long long> dist(n, LLONG_MAX), ways(n, 0);\n        dist[0] = 0;\n        ways[0] = 1;\n        pq.push({0, 0});\n        int mod = (int)(1e9 + 7);\n        while (!pq.empty()) {\n            long long dis = pq.top().first;\n            long long node = pq.top().second;\n            pq.pop();\n            if (dist[node] < dis)\n                continue;\n            for (auto it : adj[node]) {\n                long long adjNode = it.first;\n                long long edW = it.second;\n                if (dis + edW < dist[adjNode]) {\n                    dist[adjNode] = dis + edW;\n                    pq.push({dis + edW, adjNode});\n                    ways[adjNode] = ways[node];\n                } else if (dis + edW == dist[adjNode]) {\n                    ways[adjNode] = (ways[adjNode] + ways[node]) % mod;\n                }\n            }\n        }\n        return ways[n - 1] % mod;\n    }\n};\n```
['C++']