Simple Djikstra Approach✅✅
IntuitionTo count the number of different shortest paths from node 0 to node n - 1, we need more than just the shortest distances.
Dijkstra’s algorithm is ideal
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
To count the number of different shortest paths from node 0 to node n - 1, we need more than just the shortest distances. 
Dijkstra’s algorithm is ideal for finding shortest paths in weighted graphs, and we can enhance it to count the number 
of ways we can reach each node with the shortest distance.

# Approach
<!-- Describe your approach to solving the problem. -->
- Build the graph using adjacency lists with edge weights.
- Use Dijkstra's algorithm to find the shortest distance from node 0 to all nodes.
- Maintain a ways[] array where ways[i] = number of shortest paths to node i.
- Use a min-heap (priority queue) to always process the node with the smallest known distance.
- For each neighbor:
    - If a shorter path is found, update distance and ways.
    - If an equally short path is found, add the number of ways.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(E * log V), where E is the number of edges and V is the number of nodes.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(V + E), for the graph, distance array, ways array, and priority queue.

# Code
```cpp []
#define ll long long
#define pll pair<ll, ll>
class Solution {
public:
    int MOD = 1e9 + 7;
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<pll>> graph(n);
        for(auto& road: roads) {
            ll u = road[0], v = road[1], time = road[2];
            graph[u].push_back({v, time});
            graph[v].push_back({u, time});
        }
        return dijkstra(graph, n, 0);
    }
    int dijkstra(const vector<vector<pll>>& graph, int n, int src) {
        vector<ll> dist(n, LONG_MAX);
        vector<ll> ways(n);
        ways[src] = 1;
        dist[src] = 0;
        priority_queue<pll, vector<pll>, greater<>> minHeap;
        minHeap.push({0, 0}); // dist, src
        while (!minHeap.empty()) {
            auto[d, u] = minHeap.top(); minHeap.pop();
            if (d > dist[u]) continue; // Skip if `d` is not updated to latest version!
            for(auto [v, time] : graph[u]) {
                if (dist[v] > d + time) {
                    dist[v] = d + time;
                    ways[v] = ways[u];
                    minHeap.push({dist[v], v});
                } else if (dist[v] == d + time) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }
        return ways[n-1];
    }
};

['Graph', 'Topological Sort', 'Shortest Path', 'C++']