Beats 95%, DFS with Memoization, (bitwise operator explainer)
Intuition\nSince you\'re allowed to revisit nodes, you can\'t use previously visited nodes to avoid loops, instead you have to use the time_left to avoid loops,
# Intuition\nSince you\'re allowed to revisit nodes, you can\'t use previously visited nodes to avoid loops, instead you have to use the time_left to avoid loops,\nhowever, if you\'ve previously visited this node, you can\'t add it\'s value to the answer, so you still need to keep track of previously visited\n\n# Approach\nWe first create a better way to access the graph by connecting all edges in a dictionary\n\nThen we use dfs to traverse the graph, I use bitwise operators and masking because it can keep track of visited nodes while being hashable (for the lru_cache).\n\nIf you\'re back at the origin node (0), then we check if this answer is larger than what we\'ve seen previously \n\nwe go through each of the neighbors of the node, if the cost of going there is less than the time we have left, we visit it, \n\nwe check if the neighbor has been visited via & operator in the mask\n\nif it has been visited, the neighbor\'s value is 0, otherwise we just keep the neighbor\'s value.\n\n##  THE MEAT of bitwise operators and masking\nwe can use bitwise operators to track visited nodes, \nif a node has been visited we can mark it as 1\n\nie: 0010001 means, nodes 0 and nodes 4 has been visited \nbecause position 0 and position 4 in reverse is 1\n\n### Marking a node as visited\n#### we can use the | (or) operator\nin python 1 << 4 just means 1000 (1 at the 4th reversed pos)\nwe can mark a node 3 as visited by doing \nmask = 1 << 3 | mask because if mask is 10001\nthe | (or) will compare 100 and 10001 and will create a new mask with 1\nin every pos where there is a 1 in either mask\n\n### checking if a node has been visited previously\n##### **We can use the & (and) operator**\n1 << 4 means 8 which is 1000 when in binary\n**1 << 4 & 9 (1001) = True**\n because both 1000 and 1001 have 1 in the 4th position\n\nwe then update the mask with an | operator and dfs with the neighbor, remembering to use the updated mask and updating the cost, as well as adding the neighbor\'s value to the current value\n\n\n# Complexity\n- Time complexity:\nO(N or Time_left / cost of edges) we may revisit nodes, but we will only loop till we get to 0 time left\n\n- Space complexity:\nO(edges) we create a map of the edges\n\n# Code\n```\nfrom collections import defaultdict\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n        edge_map = defaultdict(dict)\n        # create a O(1) access for all edges, both ways since it\'s undirected\n        for i, j, cost in edges:\n            edge_map[i][j] = cost\n            edge_map[j][i] = cost \n\n        #original answer is just the value of node(0)\n        ans = values[0]\n\n        #lru cache for easy memoing \n        @lru_cache(None)\n        def dfs(node, value, mask, time_left):\n            #if we\'re at the origin, we check if the value exceeds our old answer\n            if node == 0:\n                nonlocal ans\n                ans = max(ans, value)\n\n            for neighbor in edge_map[node]:\n                cost = edge_map[node][neighbor]\n                #if we have enough time left for this path\n                if cost <= time_left:\n                    neighbor_value = 0 if mask & (1 << neighbor) else values[neighbor]\n                    dfs(neighbor, value + neighbor_value, mask | (1 << neighbor), time_left - cost)\n\n        dfs(0, values[0], 1, maxTime)\n        return ans\n\n\n```
['Python3']