<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>

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        # 2. Dijkstra + Min Heap + DP count number of ways
        # dis[] array to store the shortest time to reach each node
        # ways[] array to count the number of ways to reach each node in the shortest time
        # O(E*logV): E=number of edges, V=number of nodes
        # O(E+V): store adjacency lists and heap
        # step1: build graph
        graph = collections.defaultdict(list)
        for u, v, time in roads:
            graph[u].append([v, time])
            graph[v].append([u, time])
        # step2: initialize arrays to store shortest distance and number of ways
        dis = [float(inf) for _ in range(n)]    # shortest path from 0 to node
        dis[0] = 0
        ways = [0 for _ in range(n)]  # number of shortest paths from 0 to node
        ways[0] = 1     # Base Case: 1 shortest way from node 0 to 0
        
        # step3: dijkstra     
        min_heap = [[0, 0]]   # store elems [distance from 0 to i, i]
        
        while min_heap:
            cur_dis, cur_node = heapq.heappop(min_heap)
            # update neighbors of cur_node with path from start to them via cur_node
            for neighbor_node, time in graph[cur_node]:
                new_time = cur_dis + time
                # Case1: found a shorter path
                if new_time < dis[neighbor_node]:    # found a shorter way
                    # reset shortest time and number of shortest ways
                    dis[neighbor_node] = new_time
                    ways[neighbor_node] = ways[cur_node]    
                    # Important: push this shorter path to min_heap
                    heapq.heappush(min_heap, [dis[neighbor_node], neighbor_node])
                # Case2: found a equal path (Important: use elif!)
                elif new_time == dis[neighbor_node]:
                    ways[neighbor_node] += ways[cur_node]
                    ways[neighbor_node] %= (10**9 + 7)

        # step4: return number of shortest ways to n-1
        return ways[n - 1] % (10**9 + 7)




        # 1. My Approach: [TLE]DFS + Memoization
        # repeated subproblems: number of ways from i to n-1
        
        # idea1[discarded]: first find shortest distance from each i to n-1
        #   =>Problem: it's not guaranteed that the direct road from i to n-1 is the shortest, maybe i->k->n-1 is shorter than i->n-1, so you can't fill in shortest_distance from i to j by the direct road between them

        # idea2[!TLE! 4/55]: find all different ways, record count of ways for different time taken 
        # Note: want shortes path => don't go back to visited nodes, otherwise will have infinite number of roads!
        roads_dict = {}     # store direct road from i to j
        neighbors = collections.defaultdict(list)
        for start, end, time in roads:
            roads_dict[(start, end)] = time
            roads_dict[(end, start)] = time
            neighbors[start].append(end)
            neighbors[end].append(start)

        time_to_freq = {}
        min_time_seen = float("inf")
        memo = {}           # memo[i] = dict of freq of times needed from i to n-1 

        def recurse(cur_node, seen):
            nonlocal min_time_seen, n
            if cur_node == n - 1:       # reach destination
                # min_time_seen = min(min_time_seen, time_sofar)
                # if time_sofar == min_time_seen:
                #     time_to_freq[time_sofar] += 1
                return {0: 1}
            if cur_node in memo:
                return memo[cur_node]
            cur_res = collections.defaultdict(int)
            for neighbor in neighbors[cur_node]:
                if neighbor not in seen:    # can go to this neighbor
                    cur_time = roads_dict[(cur_node, neighbor)] # time from cur to neigh
                    seen.add(cur_node)
                    rest_dict = recurse(neighbor, seen)         # Recursive Call
                    for rest_time, count in rest_dict.items():
                        cur_res[rest_time + cur_time] += count
                        cur_res[rest_time + cur_time] %= 10**9 + 7
                    seen.remove(cur_node)                       # Backtrack
            return cur_res

        counts = recurse(0, set())
        return counts[min(counts.keys())]
            


        
259