Simple Dijkstra || Easy Explanation
IntuitionYou're given a weighted undirected graph with n nodes and some roads between them. You want to:
Find the number of different shortest paths from node 0
# Intuition
You're given a weighted undirected graph with n nodes and some roads between them. You want to:
- Find the number of different shortest paths from node 0 to node n - 1.

It's not just about the shortest path length, but how many ways you can achieve that shortest time.

# Approach
Imagine you're running Dijkstra’s algorithm to find the shortest distance from node 0 to all nodes. While doing this, you also:
- Track how many ways you can reach each node with the minimum possible time.
- Whenever you find a shorter path to a node, update both:
    - dist[node]: shortest time
    - ways[node]: number of ways to reach with that time

Whenever you find a path with the same time as the current minimum:
- Add the number of ways from the previous node (ways[current]) to ways[adjacent].

This lets you count all distinct shortest paths.

# Complexity
- Time complexity:
    - **Dijkstra:** O((E + V) log V)

- Space complexity:
    - O(V + E)

# Code
```cpp []
int mod = (1e9+7);

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        //Bi-directional
        vector<pair<int , int>> adj[n];
        for(auto& it : roads)
        {
            adj[it[0]].push_back({it[1],it[2]});
            adj[it[1]].push_back({it[0],it[2]});            
        }
        //min heap 
        priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,
         greater<pair<long long,long long>>> store;
         
        store.push({0,0});

        vector<long long> dist(n,LONG_MAX);
        dist[0] = 0;
        
        vector<long long> ways(n,0);
        ways[0] = 1;
        
        while(!store.empty())
        {
            long long time = store.top().first;
            long long node = store.top().second;
            store.pop();

            for(auto& it : adj[node])
            {
                long long adjnode = it.first;
                long long time_needed = it.second;
                
                if(time_needed + time < dist[adjnode])
                {
                    dist[adjnode] = time_needed + time;
                    store.push({time_needed + time , adjnode});
                    ways[adjnode] = ways[node];
                }
                else if(time_needed + time == dist[adjnode])
                {
                    ways[adjnode] = (ways[adjnode] + ways[node]) % mod;
                }
            }
        }
        return ways[n-1];
    }
};
```
['Graph', 'Shortest Path', 'C++']