BFS 177ms Beats 100.00%of users with Python3
Intuition\nGraph question - first think about using BFS\n\n# Approach\nBFS\n\n# Complexity\n\n\n# Code\n\nclass Solution:\n    def maximalPathQuality(self, valu
# Intuition\nGraph question - first think about using BFS\n\n# Approach\nBFS\n\n# Complexity\n![Screenshot 2023-07-18 at 3.40.29 PM.png](https://assets.leetcode.com/users/images/7305d8e8-92d6-4b5e-be59-a806c94ce0db_1689720115.546126.png)\n\n# Code\n```\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n\n        graph = collections.defaultdict(list)\n        for u, v, t in edges :\n            graph[u].append((v,t))\n            graph[v].append((u,t))\n\n        queue = collections.deque([(0, 0, values[0], [0])]) # (node, time, totalVal, path)\n        valList = [(-1,-1)]*len(values)\n        valList[0] = (values[0], 0)\n        output = 0\n        while queue :\n            node, curTime, curVal, visited = queue.popleft()\n            if node == 0 :\n                output = max(output, curVal)\n            for nxt, t in graph[node] :\n                if curTime + t > maxTime :\n                    continue\n                nxtVal = curVal\n                if nxt not in visited:\n                    nxtVal += values[nxt]\n                #This is the condition that significantly reduces the runtime\n                if curTime+t >= valList[nxt][1] and nxtVal < valList[nxt][0] :\n                    continue\n                queue.append((nxt, curTime+t, nxtVal, visited + [nxt]))\n                valList[nxt] = (nxtVal, curTime+t)\n        return output\n\n```
['Breadth-First Search', 'Python', 'Python3']