🔥 Dijkstra's Algorithm | 🚀 Priority Queue | ⏱️ TC: O(E log V) 🎯
IntuitionWe use Dijkstra's algorithm to find the shortest paths and simultaneously count how many different ways we can reach each node with the current shortes
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We use **Dijkstra's algorithm** to find the shortest paths and simultaneously count how many different ways we can reach each node with the current shortest distance.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Build the Graph: Create an adjacency list representation of the graph where for each node, we store its neighbors and the time to reach them.
2. Create a dist array to store the shortest distance to each node (initially infinity, except dist[0] = 0)
3. Create a ways array to count the number of ways to reach each node via the shortest path (initially ways[0] = 1, others = 0)
4. Use a priority queue to explore nodes in order of increasing distance
5. For each node, look at all its neighbors
     - If we find a shorter path to a neighbor, update its distance and reset its count of ways
    - If we find a path of equal length, add the current node's count to the neighbor's count

6. Result: After the algorithm completes, ways[n-1] contains the number of shortest paths from node 0 to node n-1.
# Complexity
- Time complexity: O(E log V)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(V + E)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        adj = defaultdict(list)
        for u, v, time in roads:
            adj[u].append((v, time))
            adj[v].append((u, time))
            
        dist = [0]+[float('inf')]*(n-1)
        ways = [1]+[0]*(n-1)
        
        pq = [(0, 0)]  #(time, node)
        MOD = 10**9 + 7 
        
        # Dijkstra's algorithm
        while pq:
            d, node = heapq.heappop(pq)
            
            if d > dist[node]:
                continue
                
            for nei,t in adj[node]:
                if dist[node]+t < dist[nei]:
                    dist[nei] = dist[node]+t
                    ways[nei] = ways[node]
                    heapq.heappush(pq, (dist[nei], nei))
                elif dist[node]+t == dist[nei]:
                    ways[nei] = (ways[nei] + ways[node]) % MOD
        
        return ways[n-1]
```
![upvote.jpeg](https://assets.leetcode.com/users/images/988d4cd2-bb4f-4d28-bdac-7b5e5ca70954_1742717858.2368653.jpeg)


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