2065. Maximum Path Quality of a Graph
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
from collections import defaultdict, deque

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        graph = defaultdict(list)
        
        for u, v, time in edges:
            graph[u].append((v, time))
            graph[v].append((u, time))

        queue = deque([(0, 0, values[0], {0})])  # node, time spent, quality, visited nodes
        state_cache = {}
        max_result = 0
        
        while queue:
            node, time_spent, quality, visited_nodes = queue.popleft()
            
            if node in state_cache:
                prev_time, prev_quality = state_cache[node]
                if prev_time <= time_spent and prev_quality >= quality:
                    continue
            state_cache[node] = (time_spent, quality)
            
            if time_spent > maxTime:
                continue

            if node == 0:
                max_result = max(max_result, quality)

            for neighbor, travel_time in graph[node]:
                new_visited_nodes = visited_nodes.copy()
                if neighbor not in visited_nodes:
                    new_visited_nodes.add(neighbor)
                    new_quality = quality + values[neighbor]
                else:
                    new_quality = quality
                queue.append((neighbor, time_spent + travel_time, new_quality, new_visited_nodes))
        
        return max_result

```
['Python3']