Python3 - Modified Djikstra's
The problem is very similar to cheapest flight within K stops.\nhttps://leetcode.com/problems/cheapest-flights-within-k-stops/ \n\n\n\n\nclass Solution:\n    de
The problem is very similar to cheapest flight within K stops.\nhttps://leetcode.com/problems/cheapest-flights-within-k-stops/ \n\n\n\n```\nclass Solution:\n    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:\n        n = len(passingFees)\n        \n        g = [[] for i in range(n)]\n        for e in edges:\n            g[e[0]].append((e[1], e[2]))\n            g[e[1]].append((e[0], e[2]))\n            \n        times = {}\n        \n        pq = [(passingFees[0],0,0)]\n        \n        while pq:\n            cost, node, time = heapq.heappop(pq)\n            \n            if time > maxTime:\n                continue\n            \n            if node == n-1:\n                return cost\n            \n            if node not in times or times[node] > time:\n                times[node] = time\n                for nbor, trip in g[node]:\n                    heapq.heappush(pq, (passingFees[nbor]+cost, nbor, time+trip))\n            \n            \n    \n        return -1\n```\n\nEdit - A lot of folks have question over why we need to consider costlier routes later for the same node. Hope the below image clarifies those questions.\n\n\n![image](https://assets.leetcode.com/users/images/9a025b9e-4e77-4fe3-bfb4-c05ee4185f4e_1626046391.5261254.jpeg)\n\n\nIn this image - B is discovered first via the node A1, but the route A1-B-C does not meet the time constraint. \n\nThen B is again discovered via the node A2, this time the cost is more, but the time to reach C via A2-B-C meets the time constraint.\n\n
[]