# 2065. Maximum Path Quality of a Graph

## Approach 1: DFS

• Time: $O(|V| + |E|)$, where $|V| = |\texttt{values}|$ and $|E| = |\texttt{edges}|$
• Space: $O(|V| + |E|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: int maximalPathQuality(vector& values, vector>& edges, int maxTime) { const int n = values.size(); int ans = 0; vector>> graph(n); vector seen(n); seen[0] = 1; for (const vector& edge : edges) { const int u = edge[0]; const int v = edge[1]; const int time = edge[2]; graph[u].emplace_back(v, time); graph[v].emplace_back(u, time); } dfs(graph, values, 0, values[0], maxTime, seen, ans); return ans; } private: void dfs(const vector>>& graph, const vector& values, int u, int quality, int remainingTime, vector& seen, int& ans) { if (u == 0) ans = max(ans, quality); for (const auto& [v, time] : graph[u]) { if (time > remainingTime) continue; const int newQuality = quality + values[v] * (seen[v] == 0); ++seen[v]; dfs(graph, values, v, newQuality, remainingTime - time, seen, ans); --seen[v]; } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public int maximalPathQuality(int[] values, int[][] edges, int maxTime) { final int n = values.length; List>[] graph = new List[n]; int[] seen = new int[n]; seen[0] = 1; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] edge : edges) { final int u = edge[0]; final int v = edge[1]; final int time = edge[2]; graph[u].add(new Pair<>(v, time)); graph[v].add(new Pair<>(u, time)); } dfs(graph, values, 0, values[0], maxTime, seen); return ans; } private int ans = 0; private void dfs(List>[] graph, int[] values, int u, int quality, int remainingTime, int[] seen) { if (u == 0) ans = Math.max(ans, quality); for (Pair pair : graph[u]) { final int v = pair.getKey(); final int time = pair.getValue(); if (time > remainingTime) continue; final int newQuality = quality + values[v] * (seen[v] == 0 ? 1 : 0); ++seen[v]; dfs(graph, values, v, newQuality, remainingTime - time, seen); --seen[v]; } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int: n = len(values) ans = 0 graph = [[] for _ in range(n)] seen = [0] * n seen[0] = 1 for u, v, time in edges: graph[u].append((v, time)) graph[v].append((u, time)) def dfs(u: int, quality: int, remainingTime: int): nonlocal ans if u == 0: ans = max(ans, quality) for v, time in graph[u]: if time > remainingTime: continue newQuality = quality + values[v] * (seen[v] == 0) seen[v] += 1 dfs(v, newQuality, remainingTime - time) seen[v] -= 1 dfs(0, values[0], maxTime) return ans 

## Approach 2: BFS

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int: ans = 0 graph = [[] for _ in range(len(values))] # (node, quality, remainingTime, seen) q = collections.deque([(0, values[0], maxTime, {0})]) for u, v, time in edges: graph[u].append((v, time)) graph[v].append((u, time)) while q: u, quality, remainingTime, seen = q.popleft() if u == 0: ans = max(ans, quality) for v, time in graph[u]: if time <= remainingTime: q.append( (v, quality + values[v] * (v not in seen), remainingTime - time, seen | set([v]))) return ans