EXPLAINED PYTHON SOLUTION ✅🔥 DP SOLUTION | GRAPH | TABULATION
Intuition\nIn the problem we are asked to find a path which has less than the max permitted travel time and has the minimum cost compared to other valid paths i
# Intuition\nIn the problem we are asked to find a path which has less than the max permitted travel time and has the minimum cost compared to other valid paths if any. If no such paths are available then return -1.\n\n# Approach\nWe can start by mapping the graph. We will map in a **bidirectional** way. We will initialize a 2D DP array whose **dp[i][j]** will represent the **minimum** cost of reaching *i-th* node in **j** minutes. We will the start from the 0th node and explore it\'s neighbours. We will compute the new distance as the distance to **current node + distance to the next node**. If the distance (time) is less than or equal to max permitted time then we can move to computing the new cost. New cost can be computed as **cost to get to current node + cost to next node**. If the new cost if less than the existing cost to neighbouring node with the newly computed time then we can update it\'s time and append the new node and new time to the queue. At last, If the minimum of the last row of DP array if infinity then it means it is **impossible** to reach the node in given constraints so we return -1 else return the minimum value.\n\n# Complexity\n- Time complexity: $$O(E+N*T)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(E+N*T)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom collections import deque, defaultdict\nclass Solution:\n    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:\n        graph = defaultdict(list)\n        n = len(passingFees)\n        for src, dest, time in edges:\n            graph[src].append((dest, time))\n            graph[dest].append((src, time))\n\n        dp = [[float(\'inf\')] * (maxTime + 1) for _ in range(n)]\n        dp[0][0] = passingFees[0]\n        queue = deque([(0, 0)])\n        while queue:\n            current_node, current_time = queue.popleft()\n            for nei, nei_time in graph[current_node]:\n                new_time = current_time + nei_time\n                if new_time <= maxTime:\n                    new_cost = dp[current_node][current_time] + passingFees[nei]\n                    if new_cost < dp[nei][new_time]:\n                        dp[nei][new_time] = new_cost\n                        queue.append((nei, new_time))\n        \n        min_cost = min(dp[n-1])\n        return min_cost if min_cost != float(\'inf\') else -1\n```
['Array', 'Dynamic Programming', 'Graph', 'Python', 'Python3']