<p>There is a country of <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code> where <strong>all the cities are connected</strong> by bi-directional roads. The roads are represented as a 2D integer array <code>edges</code> where <code>edges[i] = [x<sub>i</sub>, y<sub>i</sub>, time<sub>i</sub>]</code> denotes a road between cities <code>x<sub>i</sub></code> and <code>y<sub>i</sub></code> that takes <code>time<sub>i</sub></code> minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.</p>

<p>Each time you pass through a city, you must pay a passing fee. This is represented as a <strong>0-indexed</strong> integer array <code>passingFees</code> of length <code>n</code> where <code>passingFees[j]</code> is the amount of dollars you must pay when you pass through city <code>j</code>.</p>

<p>In the beginning, you are at city <code>0</code> and want to reach city <code>n - 1</code> in <code>maxTime</code><strong> minutes or less</strong>. The <strong>cost</strong> of your journey is the <strong>summation of passing fees</strong> for each city that you passed through at some moment of your journey (<strong>including</strong> the source and destination cities).</p>

<p>Given <code>maxTime</code>, <code>edges</code>, and <code>passingFees</code>, return <em>the <strong>minimum cost</strong> to complete your journey, or </em><code>-1</code><em> if you cannot complete it within </em><code>maxTime</code><em> minutes</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/leetgraph1-1.png" style="width: 371px; height: 171px;" /></p>

<pre>
<strong>Input:</strong> maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
<strong>Output:</strong> 11
<strong>Explanation:</strong> The path to take is 0 -&gt; 1 -&gt; 2 -&gt; 5, which takes 30 minutes and has $11 worth of passing fees.
</pre>

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

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/copy-of-leetgraph1-1.png" style="width: 371px; height: 171px;" /></strong></p>

<pre>
<strong>Input:</strong> maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
<strong>Output:</strong> 48
<strong>Explanation:</strong> The path to take is 0 -&gt; 3 -&gt; 4 -&gt; 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -&gt; 1 -&gt; 2 -&gt; 5 since it would take too long.
</pre>

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

<pre>
<strong>Input:</strong> maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is no way to reach city 5 from city 0 within 25 minutes.
</pre>

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

<ul>
	<li><code>1 &lt;= maxTime &lt;= 1000</code></li>
	<li><code>n == passingFees.length</code></li>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>n - 1 &lt;= edges.length &lt;= 1000</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>1 &lt;= time<sub>i</sub> &lt;= 1000</code></li>
	<li><code>1 &lt;= passingFees[j] &lt;= 1000</code>&nbsp;</li>
	<li>The graph may contain multiple edges between two nodes.</li>
	<li>The graph does not contain self loops.</li>
</ul>

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        cities = len(passingFees)

        roads = [set() for city in range(cities)]
        timeToTraverse = [[float('inf') for city2 in range(cities)] for city1 in range(cities)]
        for city1, city2, time in edges:
            roads[city1].add(city2)
            roads[city2].add(city1)
            if time < timeToTraverse[city1][city2]:
                timeToTraverse[city1][city2] = timeToTraverse[city2][city1] = time
        for city in range(cities):
            timeToTraverse[city][city] = 0
        
        minCosts = [[float('inf')] * (maxTime + 1) for city in range(cities)]
        minCosts[0][0] = passingFees[0]

        for timeToReach in range(1, maxTime + 1):
            for destCity in range(cities):
                for sourceCity in roads[destCity]:
                    if timeToReach < timeToTraverse[sourceCity][destCity]:
                        continue
                    if minCosts[sourceCity] == float('inf'):
                        continue
                    minCostFromSource = minCosts[sourceCity][timeToReach - timeToTraverse[sourceCity][destCity]] + passingFees[destCity]
                    if minCostFromSource < minCosts[destCity][timeToReach]:
                        minCosts[destCity][timeToReach] = minCostFromSource
        
        minCostToDest = min(minCosts[-1])
        return minCostToDest if minCostToDest != float('inf') else -1



    """
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        cities = len(passingFees)

        roads = [set() for city in range(cities)]
        timeToTraverse = [[float('inf') for city2 in range(cities)] for city1 in range(cities)]
        for city1, city2, time in edges:
            roads[city1].add(city2)
            roads[city2].add(city1)
            if time < timeToTraverse[city1][city2]:
                timeToTraverse[city1][city2] = timeToTraverse[city2][city1] = time
        for city in range(cities):
            timeToTraverse[city][city] = 0
        
        source, dest = 0, cities - 1
        minCosts = [[float('inf')] * (maxTime + 1) for city in range(cities)]
        visited = [[False] * (maxTime + 1) for city in range(cities)]
        minCosts[source][0] = 0
        pq = [(passingFees[source], source, 0)]

        while pq:
            cost, city, time = heapq.heappop(pq)
            if visited[city][time]:
                continue
            visited[city][time] = True
            for neighbor in roads[city]:
                timeToNeighbor = time + timeToTraverse[city][neighbor]
                if timeToNeighbor > maxTime:
                    continue
                if visited[neighbor][timeToNeighbor]:
                    continue
                if cost + passingFees[neighbor] < minCosts[neighbor][timeToNeighbor]:
                    minCosts[neighbor][timeToNeighbor] = cost + passingFees[neighbor]
                    heapq.heappush(pq, (cost + passingFees[neighbor], neighbor, timeToNeighbor))
        
        minCostToDest = min(minCosts[dest])
        return minCostToDest if minCostToDest != float('inf') else -1



    """

    """
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        cities = len(passingFees)

        roads = [set() for city in range(cities)]
        timeToTraverse = [[float('inf') for city2 in range(cities)] for city1 in range(cities)]
        for city1, city2, time in edges:
            roads[city1].add(city2)
            roads[city2].add(city1)
            if time < timeToTraverse[city1][city2]:
                timeToTraverse[city1][city2] = timeToTraverse[city2][city1] = time
        for city in range(cities):
            timeToTraverse[city][city] = 0
        
        source, dest = 0, cities - 1

        minCosts = [float('inf')] * cities
        minCosts[source] = 0
        minTimeEnqueued = [float('inf')] * cities
        pq = [(passingFees[source], source, 0)]

        while pq:
            cost, city, time = heapq.heappop(pq)
            if time >= minTimeEnqueued[city]:
                continue
            minTimeEnqueued[city] = time
            for neighbor in roads[city]:
                if time + timeToTraverse[city][neighbor] > maxTime:
                    continue
                if cost + passingFees[neighbor] < minCosts[neighbor]:
                    minCosts[neighbor] = cost + passingFees[neighbor]
                    heapq.heappush(pq, (cost + passingFees[neighbor], neighbor, time + timeToTraverse[city][neighbor]))
        
        return minCosts[dest] if minCosts[dest] != float('inf') else -1
    """


        
78200