python | BFS | 99.33% | commented
Hello, just wrote this and wanted to checkout other\'s solution, and I couldn\'t find fast BFS solutions, so I am just sharing my code.\n\nI wonder how can I no
Hello, just wrote this and wanted to checkout other\'s solution, and I couldn\'t find fast BFS solutions, so I am just sharing my code.\n\nI wonder how can I not keeping copy of set every append to queue. Please **any suggest** will be appreciated\n\n**Thought process:**\n1. build undirected graph\n2. start BFS from 0 with (current vertex / time taken so far / quality collected so far / used vertext so far for this path)\n3. **Memoization** here which let you stop if current vertext can\'t give you better result extremely accelerate the whole algorithm\n4. Also if the time taken so far is more than the limit, no need to proceed\n5. If we are at node \'0\' then let\'s keep the maximum quality points collected so far\n6. quality will only be updated if has not been collected for the path. I am copying the set to use for new path. (like I said, any suggestion to use instead of this is big thanks)\n\n```\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n        graph = defaultdict(list)\n\t\t# build graph\n        for edge in edges:\n            graph[edge[0]].append((edge[1], edge[2]))\n            graph[edge[1]].append((edge[0], edge[2]))\n        \n        q = deque()\n        q.append((0, 0, values[0], set([0])))\n        cache = {}\n        maxPoint = 0\n\t\t\n        while q:\n            currV, currTime, currPoints, currSet = q.popleft()\n            if currV in cache:\n\t\t\t\t# if vertex has been visited, and if the previousTime is \n\t\t\t\t# less or equal to current time but current points is lower?\n\t\t\t\t# then this path can\'t give us better quality so stop proceeding.\n                prevTime, prevPoints = cache[currV]\n                if prevTime <= currTime and prevPoints > currPoints:\n                    continue\n            cache[currV] = (currTime, currPoints)\n\t\t\t# can\'t go over the maxTime limit\n            if currTime > maxTime:\n                continue\n\t\t\t# collect maxPoint only if current vertex is 0\n            if currV == 0:\n                maxPoint = max(maxPoint, currPoints)\n            for neigh, neighTime in graph[currV]:\n                newSet = currSet.copy()\n\t\t\t\t# collects quality only if not collected before\n                if neigh not in currSet:\n                    newSet.add(neigh)\n                    newPoint = currPoints + values[neigh]\n                else:\n                    newPoint = currPoints\n                q.append((neigh, currTime + neighTime, newPoint, newSet))\n        return maxPoint\n```\n\n![image](https://assets.leetcode.com/users/images/c9479bfe-7695-4fec-ad77-c424e5416ec2_1650432955.8708572.png)\n\n**Please correct me if I am wrong !\nPlease UPVOTE if you find this solution helpful !\nHappy algo!**\n
['Breadth-First Search', 'Memoization', 'Python']