Graph, Dijkstra, Shortest Path, Dynamic Programming O((E+V)logV)
IntuitionTo find the number of ways to reach the destination node n - 1 from node 0 in the shortest possible time, we need more than just the shortest distance
# Intuition
To find the number of ways to reach the destination node `n - 1` from node `0` in the *shortest* possible time, we need more than just the shortest distance — we must also track **how many different paths** lead to that shortest distance.

A natural fit for shortest path problems is **Dijkstra’s algorithm**. By extending it with a `pathCount` array, we can track how many distinct paths reach each node using the current known shortest time.

# Approach
1. **Graph Representation:** First, we construct an adjacency list from the input `roads` array. Each edge is bidirectional and stores a pair `(neighbor, time)`.
2. **Dijkstra’s Algorithm:** 
   - Use a min-heap (priority queue) to explore the graph starting from node `0`.
   - Track the shortest known time to reach each node using `shortest_time` array.
   - Track the number of distinct paths that achieve this shortest time using `pathCount` array.
3. **Relaxation:** For each node processed:
   - If a neighboring node can be reached in a strictly shorter time, update the shortest time and set its path count to that of the current node.
   - If the neighboring node can be reached in **equal** shortest time, increment its path count by the current node’s count.
4. **Result:** Return the count of shortest paths to node `n - 1`, modulo \(10^9 + 7\).

# Complexity
- **Time complexity:**  
  $$O((E + V) \log V)$$  
  Where `V` is the number of intersections (nodes) and `E` is the number of roads (edges). The log factor comes from the priority queue operations.

- **Space complexity:**  
  $$O(V + E)$$  
  For the graph representation, heap, and auxiliary arrays (`shortest_time`, `pathCount`).

# Code
```python []
from typing import List
from collections import defaultdict
import heapq

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10**9 + 7

        # Build the graph
        graph = defaultdict(list)
        for u, v, time in roads:
            graph[u].append((v, time))
            graph[v].append((u, time))

        # Dijkstra's initialization
        min_heap = [(0, 0)]  # (time, node)
        shortest_time = [float('inf')] * n
        pathCount = [0] * n
        shortest_time[0] = 0
        pathCount[0] = 1

        while min_heap:
            curr_time, u = heapq.heappop(min_heap)

            # Skip if we already found a better time
            if curr_time > shortest_time[u]:
                continue

            for v, t in graph[u]:
                new_time = curr_time + t

                if new_time < shortest_time[v]:
                    shortest_time[v] = new_time
                    pathCount[v] = pathCount[u]
                    heapq.heappush(min_heap, (new_time, v))

                elif new_time == shortest_time[v]:
                    pathCount[v] = (pathCount[v] + pathCount[u]) % MOD

        return pathCount[n - 1] % MOD

['Graph', 'Shortest Path', 'Python3']