Python3 || dfs w/ mask  || T/S: 67% / 79%
Here\'s the plan:\n\n1. We construct the graph with weights\n\n2. We recursively dfs-traverse the graph, and we keep track of the time and quality as we move fr
Here\'s the plan:\n\n1. We construct the graph with weights\n\n2. We recursively dfs-traverse the graph, and we keep track of the time and quality as we move from node to node.\n3. We use a mask to determine whether we have visited the present node on this dfs; if not, we can increase the quality.\n4. If we traverse back to the zero-node, we update the maximum quality as necessary.\n\n```python3 []\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n\n        def dfs(node:int, prev_qual:int, prev_time:int, prev_mask:int)-> None:\n            \n            if node == 0: \n                self.maxQuality = max(self.maxQuality, prev_qual)\n                \n            for nxt, wgt in graph[node]:\n                if wgt > prev_time: continue\n\n                if prev_mask & (1<< nxt): qual = prev_qual\n                else: qual = prev_qual + values[nxt]\n\n                mask = prev_mask | (1<< nxt)\n                time = prev_time - wgt\n\n                dfs(nxt, qual, time, mask)\n\n            return\n\n\n        self.maxQuality = 0\n        graph = defaultdict(list)\n\n        for u, v, wgt in edges:\n            graph[u].append((v, wgt))\n            graph[v].append((u, wgt))\n        \n        dfs(0, values[0], maxTime, 1)\n        return self.maxQuality        \n```\n[https://leetcode.com/problems/maximum-path-quality-of-a-graph/submissions/1397820301/](https://leetcode.com/problems/maximum-path-quality-of-a-graph/submissions/1397820301/)\n\n\nI could be wrong, but I think that time complexity is *O*(2^*N*) and space complexity is *O*(*N*), in which *N* ~ the number of nodes in reach of the zero node within `maxTime`. (The constraints limit this quantity to no greater than 10--this fact allows the code to be a little generous with time.)
['Python3']