Python Dijkstra's Algorithm Solution with Explanation
We can simply apply Djikstra\'s Algorithm based on the cost as the key to expand paths. However, we need to prune paths that exceed the max time. As well, we mi
We can simply apply Djikstra\'s Algorithm based on the cost as the key to expand paths. However, we need to prune paths that exceed the max time. As well, we might want to revisit nodes that costed less time even though they had a higher cost. This lets us try all valid paths incase the min cost path goes past the max time limit.\n\n```\nclass Solution:\n    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:\n        n = len(passingFees)\n        heap = [(passingFees[0],0,0)] # (cost, time, curr)\n        nodeToTime = {}\n        \n        \n        edgesDict = defaultdict(list)\n        for a,b,time in edges:\n            edgesDict[a].append((b,time))\n            edgesDict[b].append((a, time))\n                \n        while heap:\n            cost, time, curr = heappop(heap)\n            \n            if time > maxTime:\n                continue\n                \n            if curr == n -  1:\n                return cost\n            \n            # No point in visting this node again if it was visited before with a lower cost AND lower time.\n            if curr not in nodeToTime or nodeToTime[curr] > time:\n                \n                nodeToTime[curr] = time\n\n                for nextNode, travelTime in edgesDict[curr]:\n                    heappush(heap, (cost + passingFees[nextNode], time + travelTime, nextNode))\n        \n        return -1\n```
[]