<p>There is an <strong>undirected</strong> graph with <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code> (<strong>inclusive</strong>). You are given a <strong>0-indexed</strong> integer array <code>values</code> where <code>values[i]</code> is the <strong>value </strong>of the <code>i<sup>th</sup></code> node. You are also given a <strong>0-indexed</strong> 2D integer array <code>edges</code>, where each <code>edges[j] = [u<sub>j</sub>, v<sub>j</sub>, time<sub>j</sub>]</code> indicates that there is an undirected edge between the nodes <code>u<sub>j</sub></code> and <code>v<sub>j</sub></code>,<sub> </sub>and it takes <code>time<sub>j</sub></code> seconds to travel between the two nodes. Finally, you are given an integer <code>maxTime</code>.</p>

<p>A <strong>valid</strong> <strong>path</strong> in the graph is any path that starts at node <code>0</code>, ends at node <code>0</code>, and takes <strong>at most</strong> <code>maxTime</code> seconds to complete. You may visit the same node multiple times. The <strong>quality</strong> of a valid path is the <strong>sum</strong> of the values of the <strong>unique nodes</strong> visited in the path (each node&#39;s value is added <strong>at most once</strong> to the sum).</p>

<p>Return <em>the <strong>maximum</strong> quality of a valid path</em>.</p>

<p><strong>Note:</strong> There are <strong>at most four</strong> edges connected to each node.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/19/ex1drawio.png" style="width: 269px; height: 170px;" />
<pre>
<strong>Input:</strong> values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
<strong>Output:</strong> 75
<strong>Explanation:</strong>
One possible path is 0 -&gt; 1 -&gt; 0 -&gt; 3 -&gt; 0. The total time taken is 10 + 10 + 10 + 10 = 40 &lt;= 49.
The nodes visited are 0, 1, and 3, giving a maximal path quality of 0 + 32 + 43 = 75.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/19/ex2drawio.png" style="width: 269px; height: 170px;" />
<pre>
<strong>Input:</strong> values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
<strong>Output:</strong> 25
<strong>Explanation:</strong>
One possible path is 0 -&gt; 3 -&gt; 0. The total time taken is 10 + 10 = 20 &lt;= 30.
The nodes visited are 0 and 3, giving a maximal path quality of 5 + 20 = 25.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/19/ex31drawio.png" style="width: 236px; height: 170px;" />
<pre>
<strong>Input:</strong> values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
<strong>Output:</strong> 7
<strong>Explanation:</strong>
One possible path is 0 -&gt; 1 -&gt; 3 -&gt; 1 -&gt; 0. The total time taken is 10 + 13 + 13 + 10 = 46 &lt;= 50.
The nodes visited are 0, 1, and 3, giving a maximal path quality of 1 + 2 + 4 = 7.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == values.length</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>0 &lt;= values[i] &lt;= 10<sup>8</sup></code></li>
	<li><code>0 &lt;= edges.length &lt;= 2000</code></li>
	<li><code>edges[j].length == 3 </code></li>
	<li><code>0 &lt;= u<sub>j </sub>&lt; v<sub>j</sub> &lt;= n - 1</code></li>
	<li><code>10 &lt;= time<sub>j</sub>, maxTime &lt;= 100</code></li>
	<li>All the pairs <code>[u<sub>j</sub>, v<sub>j</sub>]</code> are <strong>unique</strong>.</li>
	<li>There are <strong>at most four</strong> edges connected to each node.</li>
	<li>The graph may not be connected.</li>
</ul>

# # Topic:
# # DFS

# # Algorithm:
# # Pay attention to the constraints:
# # 1. "10 <= timej, maxTime <= 100": there are at most 10 steps.
# # 2. "There are at most four edges connected to each node.": at each node, there are at most 4 branches.
# # Based on the above 2 constraints, we can have at most 4^10 nodes in the decision tree and we can run a simple DFS.

# # TC: O(4 ^ 10)
# # SC: O(10 * 10) where the first 10 means the max steps (or the height of decision tree) and the second 10 means the max visited nodes.

# from collections import defaultdict

# class Solution:
#     def maximalPathQuality(self, values: list[int], edges: list[list[int]], maxTime: int) -> int:
#         adj_map = defaultdict(list)    # (node u) => [(node v, time between u and v)]
#         for n1, n2, time in edges:
#             adj_map[n1].append((n2, time))
#             adj_map[n2].append((n1, time))
        
#         max_quality = 0
#         def dfs(node: int, time: int, visited: set[int], value_sum: int) -> None:
#             nonlocal max_quality
            
#             if node == 0:
#                 max_quality = max(max_quality, value_sum)
            
#             for nei, nei_time in adj_map[node]:
#                 new_time = time + nei_time
#                 if new_time <= maxTime:
#                     dfs(nei, new_time, visited | set([nei]), value_sum + (nei not in visited) * values[nei])
        
#         dfs(0, 0, set([0]), values[0])
#         return max_quality

# ===============================================================

# Topic:
# DFS + Memoization

# Algorithm:
# The idea is similar as solution 1 but we add cache to the dfs method.
# Note the set type is not hashable, so we need to use bitmask to represent the visited nodes.

# TC: O(4 ^ 10)
# SC: O(10 * 10) where the first 10 means the max steps (or the height of decision tree) and the second 10 means the max visited nodes.

from collections import defaultdict
from functools import cache

class Solution:
    def maximalPathQuality(self, values: list[int], edges: list[list[int]], maxTime: int) -> int:
        adj_map = defaultdict(list)    # (node u) => [(node v, time between u and v)]
        for n1, n2, time in edges:
            adj_map[n1].append((n2, time))
            adj_map[n2].append((n1, time))
        
        max_quality = 0

        @cache
        def dfs(node: int, time: int, visited: int, value_sum: int) -> None:
            nonlocal max_quality
            
            if node == 0:
                max_quality = max(max_quality, value_sum)
            
            for nei, nei_time in adj_map[node]:
                new_time = time + nei_time
                new_visited = visited | (1 << nei)
                new_value_sum = value_sum + (0 if (visited & (1 << nei)) else values[nei])
                if new_time <= maxTime:
                    dfs(nei, new_time, new_visited, new_value_sum)
        
        dfs(0, 0, 1, values[0])
        return max_quality

41000