C++ Dijkstra Two Solutions
Time Complexity: O(V^2 log V) where V is the number of node and E is the edges. \nSince we push each node to the minheap only once, that why we say log(V)\nSpac
**Time Complexity: O(V^2 log V)** where V is the number of node and E is the edges. \nSince we push each node to the minheap only once, that why we say log(V)\n**Space Complexity: O(V+ E)**\n\n**Optimized Solution**\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        // Build the weighted graph\n        vector<vector<vector<int>>> graph(n);\n        for (vector<int> &road : roads) {\n            graph[road[0]].push_back({ road[2], road[1] }); // { time, node }\n            graph[road[1]].push_back({ road[2], road[0] }); // { time, node }\n        }\n        \n        // We will use a min-heap sorted by total time: { total time, node }\n        priority_queue<vector<long long>, vector<vector<long long>>, greater<>> minheap;\n        \n        // Start with the initial node\n        minheap.push({ 0, 0 }); // { time, node }\n        \n        // Distances table for Dijkstra, dist[i] gives the shortest path between src to node_i\n        vector<long long> dist(n, LLONG_MAX);\n        \n        // Number of ways to reach a node via shortest path\n        vector<long long> ways(n, 0);\n        \n        dist[0] = 0;\n        ways[0] = 1;\n        long long mod = 1000000007;\n        \n        while (!minheap.empty()) {\n            // Get the current minimum time and node\n            long long totalDist = minheap.top()[0];\n            long long currentNode = minheap.top()[1];\n            minheap.pop();\n            \n            // Optimization, we don\'t need the distances greater than the one previously found \n            if (totalDist > dist[currentNode]) {\n                continue;\n            }\n            \n            // Check the neighbors and update dist value of the neighbors of the picked vertex\n            for (vector<int> &neigh : graph[currentNode]) {\n                // Relaxation, update the dist if neighbor is not visited and the new cost is smaller than the prev\n                int neighbor = neigh[1];\n                long long newDist = neigh[0] + totalDist;\n                \n                // Update the shortest path and ways\n                if (newDist < dist[neighbor]) {\n                    dist[neighbor] = newDist;\n                    ways[neighbor] = ways[currentNode];\n                    minheap.push({ dist[neighbor], neighbor });\n                }\n                \n                // Another shortest path found, increment the ways to node_i\n                else if (newDist == dist[neighbor]) {\n                    ways[neighbor] = (ways[neighbor] + ways[currentNode]) % mod;\n                }\n            }\n        }\n        \n        return ways[n - 1];\n    }\n};\n```\n\n**Initial Solution**\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        // Build the weighted graph\n        vector<vector<vector<int>>> graph(n);\n        for (vector<int> &road : roads) {\n            graph[road[0]].push_back({ road[2], road[1] }); // { time, node }\n            graph[road[1]].push_back({ road[2], road[0] }); // { time, node }\n        }\n        \n        // We will use a min-heap sorted by total time: { total time, node }\n        priority_queue<vector<long long>, vector<vector<long long>>, greater<>> minheap;\n        \n        // Start with the initial node\n        minheap.push({ 0, 0 }); // { time, node }\n        \n        // Distances table for Dijkstra, dist[i] gives the shortest path between src to node_i\n        vector<long long> dist(n, LLONG_MAX);\n        \n        // Number of ways to reach a node via shortest path\n        vector<long long> ways(n, 0);\n        \n        dist[0] = 0;\n        ways[0] = 1;\n        long long mod = 1000000007;\n        \n        while (!minheap.empty()) {\n            // Get the current minimum time and node\n            long long totalDist = minheap.top()[0];\n            long long currentNode = minheap.top()[1];\n            minheap.pop();\n            \n            // Check the neighbors and update dist value of the neighbors of the picked vertex\n            for (vector<int> &neigh : graph[currentNode]) {\n                // Relaxation, update the dist if neighbor is not visited and the new cost is smaller than the prev\n                int neighbor = neigh[1];\n                long long newDist = neigh[0] + totalDist;\n                \n                // Update the shortest path and ways\n                if (newDist < dist[neighbor]) {\n                    dist[neighbor] = newDist;\n                    ways[neighbor] = ways[currentNode];\n                    minheap.push({ dist[neighbor], neighbor });\n                }\n                \n                // Another shortest path found, increment the ways to node_i\n                else if (newDist == dist[neighbor]) {\n                    ways[neighbor] = (ways[neighbor] + ways[currentNode]) % mod;\n                }\n            }\n        }\n        \n        return ways[n - 1];\n    }\n};\n```
['C']