[Python] short dfs, explained
Key to success in this problem is to read problem constraints carefully: I spend like 10 minutes before I understand that problem can be solved using very simpl
Key to success in this problem is to read problem constraints carefully: I spend like 10 minutes before I understand that problem can be solved using very simple dfs. Why? Because it is given that `maxTime <= 100` and `time_j >= 10`. It means that we can make no more than `10` steps in our graph! So, all we need to do is to run `dfs(node, visited, gain, cost)`, where:\n\n1. `node` is current node we are in.\n2. `visited` is set of visited nodes: we need to keep set, because we count visitet nodes only once.\n3. `gain` is total gain we have so far.\n4. `cost` is how much time we still have.\n\n#### Complexity\nWe have at most `10` steps, and it is also given that each node have at most degree `4`, so in total we can make no more than `4^10` states. That is why we will not get TLE.\n\n#### Code\n```python\nclass Solution:\n    def maximalPathQuality(self, values, E, maxTime):\n        G = defaultdict(list)\n        for x, y, w in E:\n            G[x].append((y, w))\n            G[y].append((x, w))\n            \n        def dfs(node, visited, gain, cost):\n            if node == 0: self.ans = max(self.ans, gain)\n            for neib, w in G[node]:\n                if w <= cost:\n                    dfs(neib, visited | set([neib]), gain + (neib not in visited) * values[neib], cost - w)\n\n        self.ans = 0\n        dfs(0, set([0]), values[0], maxTime)\n        return self.ans\n```\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Depth-First Search']