1976. Number of Ways to Arrive at Destination [C++]
IntuitionTo find the number of shortest paths from node 0 to node n - 1, we need a way to not only compute the shortest distances but also count how many such p

# Intuition
To find the number of shortest paths from node 0 to node n - 1, we need a way to not only compute the shortest distances but also count how many such paths exist. A modified Dijkstra's algorithm allows us to achieve both goals simultaneously.

# Approach
We represent the graph using an adjacency list and initialize the distance to all nodes as infinite except the start node (node 0), which is set to 0. We also keep a `ways` array to count the number of shortest paths to each node. As we run Dijkstra's algorithm using a min-heap (priority queue), we update both the shortest distances and the number of ways to reach each node. If we find a shorter path to a node, we update both its distance and path count. If we find an alternative path with the same minimum distance, we add to the path count modulo \(10^9 + 7\).

# Complexity
- Time complexity:  
  $$O((E + V) \log V)$$  
  where \(V\) is the number of nodes and \(E\) is the number of roads (edges). This is due to Dijkstra's algorithm with a min-heap.

- Space complexity:  
  $$O(E + V)$$  
  for the graph representation, distance array, ways array, and priority queue.

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

        vector<long long> dist(n, LLONG_MAX);
        vector<int> ways(n, 0);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;

        dist[0] = 0;
        ways[0] = 1;
        pq.emplace(0, 0);

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            if (d > dist[u]) continue;

            for (auto& [v, t] : graph[u]) {
                long long newDist = d + t;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    ways[v] = ways[u];
                    pq.emplace(newDist, v);
                } else if (newDist == dist[v]) {
                    ways[v] = (ways[v] + ways[u]) % MOD;
                }
            }
        }

        return ways[n - 1];
    }
};
```
['C++']