class Solution:
def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
n = len(values)
G = [[] for _ in range(n)]
for u, v, w in edges:
G[u].append((v, w)) ; G[v].append((u, w))
self.res = 0
seen = {0}
def dfs(node, quality, time):
if node == 0:
self.res = max(self.res, quality)
for nbr, nbr_time in G[node]:
new_time = time + nbr_time
if new_time > maxTime: continue
visited = nbr in seen
seen.add(nbr)
dfs(nbr, quality + (0 if visited else values[nbr]), new_time)
if not visited: seen.remove(nbr)
dfs(0, values[0], 0)
return self.res
def maximalPathQuality3(self, values, E, maxTime):
G = defaultdict(list)
for x, y, w in E:
G[x].append((y, w)) ; G[y].append((x, w))
def dfs(node, visited, gain, cost):
if node == 0: self.ans = max(self.ans, gain)
for neighbor, w in G[node]:
if w <= cost:
# | to add unique elements into the seen set, without actually changing the seen set, as later we may backtrack from this path
dfs(neighbor, visited | set([neighbor]), gain + (neighbor not in visited) * values[neighbor], cost - w)
self.ans = 0
dfs(0, set([0]), values[0], maxTime)
return self.ans
def maximalPathQuality2(self, A, edges, maxTime):
G = defaultdict(dict)
for i, j, t in edges:
G[i][j] = G[j][i] = t
def dfs(i, seen, time):
res = sum(A[j] for j in seen) if i == 0 else 0
for j in G[i]:
if time >= G[i][j]:
res = max(res, dfs(j, seen | {j}, time - G[i][j]))
return res
return dfs(0, {0}, maxTime)