[C++] Dijkstra  | Clean Code | Video Solution with Diagram
Complete Video Solution with full explanationIntuitionThe problem requires finding the shortest path from node 0 to node n-1 while also counting how many differ
# Complete Video Solution with full explanation
https://youtu.be/qJfun8H8T-A

# Intuition
The problem requires finding the shortest path from node 0 to node n-1 while also counting how many different ways exist to reach the destination in the shortest possible time.

Since the graph consists of weighted edges (time taken between intersections), the most efficient way to solve this problem is Dijkstra’s Algorithm, which finds the shortest path in a weighted graph.

However, we also need to track the number of ways to reach each node in the shortest time, which requires an additional count vector.

# Approach
1. Graph Representation
Convert the roads list into an adjacency list where each node stores its connected nodes along with the respective travel time.

2. Dijkstra’s Algorithm (Modified)

Use a min-heap (priority queue) to always process the node with the shortest known distance first.

Maintain an array shortestTime[i], which stores the minimum time required to reach node i.

Maintain another array ways[i] to track the number of ways to reach node i using the shortest time.

3. Processing Nodes

Start from node 0 with a time of 0 (shortestTime[0] = 0 and ways[0] = 1).

For each node u, check all its neighbors (v, time).

If reaching v via u results in a shorter time, update shortestTime[v] and set ways[v] = ways[u].

If reaching v via u results in the same shortest time, increment ways[v] by ways[u].

Continue until all nodes are processed.

4. Final Output

The value ways[n-1] gives the number of ways to reach the destination n-1 in the shortest time.

# Complexity
- Time complexity:
Since we use Dijkstra’s Algorithm with a priority queue, the time complexity is: 𝑂((𝑉+𝐸)log𝑉)
Extracting from the priority queue takes O(log V), and we do this for all nodes (O(V log V)).

Each edge is processed once (O(E log V)).
- Space complexity:
The adjacency list takes O(V+E).

The shortestTime and ways arrays take O(V).

The priority queue takes up to O(V).

# Code
```cpp []
class Solution {
public:
    int MOD = 1e9 + 7;
    
    int countPaths(int n, vector<vector<int>>& roads) {
        // Graph Representation: Adjacency List
        vector<vector<pair<int, int>>> graph(n);
        for (auto& road : roads) {
            graph[road[0]].emplace_back(road[1], road[2]);
            graph[road[1]].emplace_back(road[0], road[2]);
        }

        // Min-Heap {shortestTime, node}
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> minHeap;
        vector<long long> shortestTime(n, LLONG_MAX);
        vector<int> ways(n, 0);

        // Initial Conditions
        shortestTime[0] = 0;
        ways[0] = 1;
        minHeap.emplace(0, 0);

        while (!minHeap.empty()) {
            auto [time, node] = minHeap.top();
            minHeap.pop();

            if (time > shortestTime[node]) continue;  // Ignore outdated states

            for (auto [neighbor, travelTime] : graph[node]) {
                long long newTime = time + travelTime;

                // Found a shorter path
                if (newTime < shortestTime[neighbor]) {
                    shortestTime[neighbor] = newTime;
                    ways[neighbor] = ways[node];  // Reset the ways count
                    minHeap.emplace(newTime, neighbor);
                }
                // Found an equally short path
                else if (newTime == shortestTime[neighbor]) {
                    ways[neighbor] = (ways[neighbor] + ways[node]) % MOD;
                }
            }
        }

        return ways[n - 1];
    }
};

```
['C++']