Python | Top 99.6%, 196ms | DFS + Caching + Dijkstra
Initially, we can just write a DFS. Something like this:\n\n\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTi
Initially, we can just write a DFS. Something like this:\n\n```\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n        neighbours = defaultdict(list)\n        for v,w,t in edges:\n            neighbours[v].append((w,t))\n            neighbours[w].append((v,t))\n            \n        def dfs(time, quality, visited, node):\n            q = quality if node == 0 else -float("inf")\n            for nb,t in neighbours[node]:\n                if time+t <= maxTime:\n                    res = dfs(time+t, quality, visited | set([nb]), nb)\n                    q = max(q, res if nb in visited else res+values[nb])\n            return q\n                \n        return dfs(0, values[0], set([0]), 0)\n```\n\nThis code is already fast enough to get an `Accepted`, but it takes 2912ms.\n\nWe can speed this up by adding some caching. We can use `@cache` from `functools` to do this. However, `@cache` requires that all function parameters, in this case `time`, `quality`, `visited`, `node`, are hashable types, and `visited` is a set and therefore not hashable. We can fix this by using an int to store the visited nodes. Ints are hashable, and thus we can use caching now. The dfs now looks like this:\n\n```\n        @cache\n        def dfs(time, quality, visited, node):\n            q = quality if node == 0 else -float("inf")\n            for nb,t in neighbours[node]:\n                if time+t <= maxTime:\n                    res = dfs(time+t, quality, visited | (1<<nb), nb)\n                    q = max(q, res if (visited >> nb) & 1 else res+values[nb])\n            return q\n                \n        return dfs(0, values[0], 1, 0)\n```\n\nThis code brings us down from 2912ms to 296ms, which was faster than 96.89% of sumissions. We can still speed it up further though. Observe the following lines from the dfs:\n\n```\n            for nb,t in neighbours[node]:\n                if time+t <= maxTime:\n```\n\nWe have this `if`-statement because we only want to recurse to neighbours that we can reach within `maxTime` seconds. However, note that if we go to such a neighbour, we *also* have to be able to go all the way back to our end node, node 0, within `maxTime`. Therefore, we can change it to:\n\n```\n            for nb,t in neighbours[node]:\n                if time+t+timeFrom0ToNb <= maxTime:\n```\n\nWe can use Dijkstras algorithm to calculate `timeFrom0ToNb` for all nodes in the graph. We then arrive at the final submission:\n\n```\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n        neighbours = defaultdict(list)\n        for v,w,t in edges:\n            neighbours[v].append((w,t))\n            neighbours[w].append((v,t))\n            \n        times = defaultdict(lambda: float("inf"))\n        q = [(0, 0)]\n        while len(q):\n            time, node = heappop(q)\n            if times[(node,0)] == float("inf"):\n                times[(node,0)] = time\n                for nb,t in neighbours[node]:\n                    if time+t <= maxTime//2 and times[(nb,0)] == float("inf"):\n                        heappush(q, (time+t, nb))\n            \n        @cache\n        def dfs(time, quality, visited, node):\n            q = quality if node == 0 else -float("inf")\n            for nb,t in neighbours[node]:\n                if time+t+times[(nb,0)] <= maxTime:\n                    res = dfs(time+t, quality, visited | (1<<nb), nb)\n                    q = max(q, res if (visited >> nb) & 1 else res+values[nb])\n            return q\n                \n        return dfs(0, values[0], 1, 0)\n```\n\nThis submission took 196ms, and was faster than 99.6% of submissions.
['Dynamic Programming', 'Depth-First Search']