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

'''
its a good point that one clarifying question for graphs is 
1) only one edge between any two nodes? or can we have different edge weights
2) all positive weights? 
3) self cycles? 
4) single component? (can reach any intersection from any other intersection)
5) directed/ undirected?

do we take dijkstras to get the shortest, then do a BFS on all paths and keep all
that have time <= target, and finally == target? 
a BFS here is VE for both time and space
and dijkstras is (V+E)logV, V +E in space

so if you BFS here its going to be waaay huge
unless you use dijkstras on the second pass
then perhaps you can 
oh then you can do it in one pass
because once you reach n - 1 
the question is can you use dijkstras to count the number of ways to reach a node
then ofc just record the min 

I think the main thing is that if you can reach an intermediate node with a higher cost
then that is not going to lead to the shortest path
so we exclude that from contributing to counts as well 
so we want the number of ways to reach all intermediate nodes that is the shortest
distance to that node 
so I'm thinking in the first pass, use dijkstras to get the shortest to every node
then second pass count number of ways to hit shortest for every node
if parent node to child node, add the parent count to child count, so long as its 
cost == shortest path to reach child 
'''
'''
whta... its just vanilla dijkstras with a tweak
basically how can we add counts to dijkstras? 
uhhhhh...

'''
class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        def dijkstras(start, end):
            #distances tracks the min dist to reach node i for i = [0, n - 1]
            distances = [inf for _ in range(n)]
            counts = [0 for _ in range(n)]
            distances[0] = 0
            counts[0] = 1
            min_heap = [(0, 0)]
            while min_heap:
                distance, node = heapq.heappop(min_heap)
                #ignore if its a duplicate
                if distances[node] < distance: continue

                for child, child_time in children[node]:
                    next_distance = child_time + distance
                    if distances[child] > next_distance:
                        distances[child] = next_distance
                        #first time?
                        counts[child] = counts[node]
                        heapq.heappush(min_heap, (next_distance, child)) 
                    elif distances[child] == next_distance:
                        counts[child] = (counts[child] + counts[node]) % MOD

            return counts[n - 1]

        #build graph
        children = collections.defaultdict(list)
        for node_1, node_2, time in roads:
            children[node_1].append((node_2, time))
            children[node_2].append((node_1, time))

        #dijkstras to get shortest distances
        return dijkstras(0, n - 1)
        
270