Maximum Path Quality of a Graph
Problem
An undirected graph has n nodes. values[i] is the value of node i, and each edge [u, v, time] takes time seconds to cross. A valid path starts at node 0, ends at node 0, and takes at most maxTime seconds; you may revisit nodes. The quality of a path is the sum of the values of the unique nodes it visits (each value counted at most once). Return the maximum quality of any valid path.
Each node has at most four incident edges, and every edge costs at least 10 seconds while maxTime ≤ 100, so any valid path crosses at most ten edges — the search space is small enough to explore exhaustively.
values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 4975def maximalPathQuality(values, edges, maxTime):
n = len(values)
adj = [[] for _ in range(n)] # adjacency list
for u, v, t in edges:
adj[u].append((v, t))
adj[v].append((u, t))
visited = [False] * n
best = 0
def dfs(node, time_left, quality):
nonlocal best
if node == 0: # back at start: candidate answer
best = max(best, quality)
for nxt, cost in adj[node]:
if cost <= time_left: # enough time to cross
seen = visited[nxt]
gain = 0 if seen else values[nxt]
visited[nxt] = True # mark before recursing
dfs(nxt, time_left - cost, quality + gain)
if not seen:
visited[nxt] = False # undo only what we set
visited[0] = True # node 0 starts visited
dfs(0, maxTime, values[0])
return bestfunction maximalPathQuality(values, edges, maxTime) {
const n = values.length;
const adj = Array.from({ length: n }, () => []); // adjacency list
for (const [u, v, t] of edges) {
adj[u].push([v, t]);
adj[v].push([u, t]);
}
const visited = new Array(n).fill(false);
let best = 0;
function dfs(node, timeLeft, quality) {
if (node === 0) best = Math.max(best, quality); // candidate answer
for (const [nxt, cost] of adj[node]) {
if (cost <= timeLeft) { // enough time to cross
const seen = visited[nxt];
const gain = seen ? 0 : values[nxt];
visited[nxt] = true; // mark before recursing
dfs(nxt, timeLeft - cost, quality + gain);
if (!seen) visited[nxt] = false; // undo only what we set
}
}
}
visited[0] = true; // node 0 starts visited
dfs(0, maxTime, values[0]);
return best;
}int best;
int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
int n = values.length;
List<int[]>[] adj = new List[n]; // adjacency list
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) {
adj[e[0]].add(new int[]{e[1], e[2]});
adj[e[1]].add(new int[]{e[0], e[2]});
}
boolean[] visited = new boolean[n];
best = 0;
visited[0] = true; // node 0 starts visited
dfs(adj, values, visited, 0, maxTime, values[0]);
return best;
}
void dfs(List<int[]>[] adj, int[] values, boolean[] visited,
int node, int timeLeft, int quality) {
if (node == 0) best = Math.max(best, quality); // candidate answer
for (int[] nb : adj[node]) {
int nxt = nb[0], cost = nb[1];
if (cost <= timeLeft) { // enough time to cross
boolean seen = visited[nxt];
int gain = seen ? 0 : values[nxt];
visited[nxt] = true; // mark before recursing
dfs(adj, values, visited, nxt, timeLeft - cost, quality + gain);
if (!seen) visited[nxt] = false; // undo only what we set
}
}
}int best = 0;
void dfs(vector<vector<pair<int,int>>>& adj, vector<int>& values,
vector<bool>& visited, int node, int timeLeft, int quality) {
if (node == 0) best = max(best, quality); // candidate answer
for (auto& [nxt, cost] : adj[node]) {
if (cost <= timeLeft) { // enough time to cross
bool seen = visited[nxt];
int gain = seen ? 0 : values[nxt];
visited[nxt] = true; // mark before recursing
dfs(adj, values, visited, nxt, timeLeft - cost, quality + gain);
if (!seen) visited[nxt] = false; // undo only what we set
}
}
}
int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
int n = values.size();
vector<vector<pair<int,int>>> adj(n); // adjacency list
for (auto& e : edges) {
adj[e[0]].push_back({e[1], e[2]});
adj[e[1]].push_back({e[0], e[2]});
}
vector<bool> visited(n, false);
best = 0;
visited[0] = true; // node 0 starts visited
dfs(adj, values, visited, 0, maxTime, values[0]);
return best;
}Explanation
The constraints are the key hint. Every edge costs at least 10 seconds and maxTime is at most 100, so any valid walk crosses at most ten edges. Combined with the rule that each node touches at most four edges, the number of distinct walks from node 0 is tiny — we can simply enumerate them all with depth-first backtracking.
We build an undirected adjacency list, then run a recursive dfs(node, time_left, quality). The state we carry is: where we currently stand, how much time budget remains, and the quality accumulated so far (the sum of values of the unique nodes we have marked).
At every entry to dfs, if we are standing on node 0 the walk so far is a valid path (it both starts and ends at 0), so we update best. This check runs at each return-to-zero, which is why pacing out and back repeatedly is captured.
For each neighbour reachable within the remaining time, we recurse. The careful part is the visited bookkeeping: a node's value should be counted only the first time it is reached. We remember whether the neighbour was seen already; we add its value to quality only when it was not, mark it visited, recurse, and on the way back we unmark it only if this call was the one that marked it. That keeps the visited set and the quality perfectly in sync across the backtracking.
For the example values = [0,32,10,43] with edges 0-1 (10), 1-2 (15), 0-3 (10) and maxTime = 49, the best walk is 0 → 1 → 0 → 3 → 0, costing 40 seconds and collecting nodes {0, 1, 3} for quality 0 + 32 + 43 = 75.