C++ Solution || Detailed Explanation
IntuitionThe problem requires us to count the number of ways to reach the last node from the first node using the shortest path. This can be achieved using Dijk
# Intuition
The problem requires us to count the number of ways to reach the last node from the first node using the shortest path. This can be achieved using Dijkstra's algorithm while maintaining a count of paths leading to each node via the shortest distance.

# Approach
1. **Graph Representation**: Represent the graph using an adjacency list where each node stores pairs of connected nodes and their respective edge weights.
2. **Priority Queue for Dijkstra's Algorithm**:
   - Use a min-heap (`priority_queue`) to process nodes based on the shortest discovered distance.
   - Maintain a `dist` array to store the shortest distance to each node.
   - Maintain a `ways` array to store the number of ways to reach each node with the shortest path.
3. **Dijkstra's Algorithm Execution**:
   - Initialize the source node (0) with a distance of `0` and `1` way to reach it.
   - Process each node, and for each of its neighbors, update its shortest distance and count the number of ways if a new shortest path is found.
   - If another shortest path is found to the same node, add the ways from the current node to the neighbor's `ways` value.
4. **Return the number of ways** to reach the last node `(n-1)`, ensuring results are modulo `1e9 + 7`.

# Complexity
- **Time Complexity**: $$O((V + E) \log V)$$, where `V` is the number of nodes and `E` is the number of edges. Dijkstra's algorithm processes each node and edge efficiently using a priority queue.

- **Space Complexity**: $$O(V + E)$$ for storing the adjacency list, distance array, and ways array.

# Code
```cpp
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<pair<long long, long long>> adj[n];
        for (auto it : roads) {
            adj[it[0]].push_back({it[1], it[2]});
            adj[it[1]].push_back({it[0], it[2]});
        }
        priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                       greater<pair<long long, int>>>
            pq;
        pq.push({0, 0});
        vector<long long> dist(n, LONG_MAX);
        dist[0] = 0;
        vector<long long> ways(n, 0);
        ways[0] = 1;
        long long mod = 1e9 + 7;
        while (!pq.empty()) {
            auto it = pq.top();
            long long node = it.second;
            long long dis = it.first;
            pq.pop();

            for (auto it : adj[node]) {
                long long edjnode = it.first;
                long long edjwt = it.second;
                if (edjwt + dis < dist[edjnode]) {
                    dist[edjnode] = edjwt + dis;
                    pq.push({dist[edjnode], edjnode});
                    ways[edjnode] = ways[node];
                } else if (dis + edjwt == dist[edjnode]) {
                    ways[edjnode] = (ways[edjnode] + ways[node]) % mod;
                }
            }
        }
        return ways[n - 1] % mod;
    }
};
```

# Explanation
- **Graph Construction**: Convert input roads into an adjacency list.
- **Dijkstra's Algorithm**:
  - Use a priority queue to always expand the shortest known path.
  - Update distances and count paths when a new shortest distance is found.
  - If another shortest path to the same node is found, accumulate the count of ways.
- **Final Result**: The number of ways to reach the last node with the shortest path.

## Edge Cases Considered
- Single-node graphs.
- Graphs with multiple shortest paths.
- Large graphs requiring modulo arithmetic to prevent overflow.

![d3550b79-52c8-4704-846f-c00daecb5632_1737784461.667478.png](https://assets.leetcode.com/users/images/e8af88c2-7360-4d0d-a286-aaca57aa4fcf_1742703320.1235483.png)



['Dynamic Programming', 'Graph', 'Shortest Path', 'C++']