<p>You are in a city that consists of <code>n</code> intersections numbered from <code>0</code> to <code>n - 1</code> with <strong>bi-directional</strong> roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.</p>

<p>You are given an integer <code>n</code> and a 2D integer array <code>roads</code> where <code>roads[i] = [u<sub>i</sub>, v<sub>i</sub>, time<sub>i</sub>]</code> means that there is a road between intersections <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> that takes <code>time<sub>i</sub></code> minutes to travel. You want to know in how many ways you can travel from intersection <code>0</code> to intersection <code>n - 1</code> in the <strong>shortest amount of time</strong>.</p>

<p>Return <em>the <strong>number of ways</strong> you can arrive at your destination in the <strong>shortest amount of time</strong></em>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/17/graph2.png" style="width: 235px; height: 381px;" />
<pre>
<strong>Input:</strong> n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, roads = [[1,0,10]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>n - 1 &lt;= roads.length &lt;= n * (n - 1) / 2</code></li>
	<li><code>roads[i].length == 3</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>1 &lt;= time<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>u<sub>i </sub>!= v<sub>i</sub></code></li>
	<li>There is at most one road connecting any two intersections.</li>
	<li>You can reach any intersection from any other intersection.</li>
</ul>

import heapq
from collections import defaultdict, deque

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # Step 1: Build the adjacency list
        adjList = defaultdict(list)
        for u, v, w in roads:
            adjList[u].append((v, w))
            adjList[v].append((u, w))
        
        # Step 2: Dijkstra's Algorithm to find the shortest paths
        min_time = [float('inf')] * n
        count_paths = [0] * n
        min_time[0] = 0
        count_paths[0] = 1
        
        # Priority queue for Dijkstra (min heap), storing (time, node)
        pq = [(0, 0)]  # (total_time, node)
        
        while pq:
            curr_time, u = heapq.heappop(pq)
            
            # If the current time is greater than the known shortest time, skip
            if curr_time > min_time[u]:
                continue
            
            for v, w in adjList[u]:
                new_time = curr_time + w
                
                if new_time < min_time[v]:  # Found a shorter path
                    min_time[v] = new_time
                    count_paths[v] = count_paths[u]
                    heapq.heappush(pq, (new_time, v))
                elif new_time == min_time[v]:  # Found another shortest path
                    count_paths[v] = (count_paths[v] + count_paths[u]) % MOD
        
        # The result is the number of ways to reach node n-1 with the shortest time
        return count_paths[n-1]


# from collections import defaultdict

# class Solution:
#     def countPaths(self, n: int, roads: List[List[int]]) -> int:
#         MOD = 10**9 + 7
        
#         adjList = defaultdict(list)
#         result = defaultdict(int)
        
#         # Build the graph
#         for start, end, time in roads:
#             adjList[start].append([end, time])
#             adjList[end].append([start, time])
        
#         def dfs(node, total, visited):
#             if node == n - 1:
#                 result[total] += 1
#                 return
            
#             visited.add(node)
#             for dest, time in adjList[node]:
#                 if dest not in visited:  # Avoid revisiting nodes
#                     dfs(dest, total + time, visited)
#             visited.remove(node)
        
#         # Start DFS from node 0 with an empty visited set
#         dfs(0, 0, set())
#         # Example: return the number of distinct paths
#         return result[min(result.keys())]% MOD
        

252