[Python/C++] DFS with memoization and explanation
Point:\nIn between u and v there\'s no point in taking the edge that takes longer time. Since the passingFee depends on only u and v and not the edge. So take t
**Point:**\nIn between u and v there\'s no point in taking the edge that takes longer time. Since the passingFee depends on only u and v and not the edge. So take the edge that takes minimum time.\nRest is memoization on u and time. `dp[u][time]` represents minimum cost to reach edge `n-1` from vertex `u` with time `time` left\n\n### Python\n```\nimport collections\nclass Solution:\n    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:\n        graph = collections.defaultdict(lambda: collections.defaultdict(lambda: float(\'inf\')))\n        for u, v, w in edges:\n            graph[u][v] = min(graph[u][v], w)\n            graph[v][u] = min(graph[v][u], w)\n        \n        n = len(passingFees)\n        states = [[-1]*(maxTime+1) for _ in range(n)]\n        def helper(u, time):\n            if u==n-1:\n                return passingFees[u]\n            if states[u][time] != -1:\n                return states[u][time]\n            ans = float("inf")\n            for v in graph[u].keys():\n                if time-graph[u][v]>=0:\n                    val = helper(v, time-graph[u][v])\n                    ans = min(ans, val)\n            states[u][time] = ans+passingFees[u]\n            return states[u][time]\n        ans = helper(0, maxTime)\n        if ans > 10000000:\n            return -1\n        return ans\n```\n\n### C++\n```\nclass Solution {\npublic:\n    int n;\n    int helper(int u, int time, vector<vector<int>>& dp, vector<unordered_map<int, int>>& graph, vector<int>& fee){\n        if(u==n-1){\n            return fee[u];\n        }\n        if(dp[u][time] != -1){\n            return dp[u][time];\n        }\n        int ans = INT_MAX-1000;\n        for(auto &e: graph[u]){\n            if(time-e.second>=0){\n                int v = helper(e.first, time-e.second, dp, graph, fee);\n                ans = min(v, ans);\n            }\n        }\n        return dp[u][time] = ans+fee[u];\n    }\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {\n        n = passingFees.size();\n        vector<vector<int>> dp(n, vector<int>(maxTime+1, -1));\n        vector<unordered_map<int, int>> graph(n);\n        for(auto &e: edges){\n            if(graph[e[0]][e[1]]==0)\n                graph[e[0]][e[1]] = e[2];\n            else\n                graph[e[0]][e[1]] = min(e[2], graph[e[0]][e[1]]);\n            if(graph[e[1]][e[0]]==0)\n                graph[e[1]][e[0]] = e[2];\n            else\n                graph[e[1]][e[0]] = min(e[2], graph[e[1]][e[0]]);\n        }\n        int ans = helper(0, maxTime, dp, graph, passingFees);\n        return (ans>10000000)?-1:ans;\n    }\n};
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'C', 'Python']