Maximum Path Quality of a Graph

This approach significantly improves upon the brute-force DFS by incorporating two key optimizations. First, it maintains the current path's quality incrementally, avoiding costly O(N) recalculations. Second, and more importantly, it uses a powerful pruning strategy. By pre-calculating the shortest time from every node back to node 0 using Dijkstra's algorithm, it can intelligently discard paths that have no chance of returning to the origin within the maxTime limit. This drastically reduces the search space.

• Build an adjacency list adj for the graph.
• Use Dijkstra's algorithm starting from node 0 to precompute minTimeToZero[i], the shortest time from every node i to node 0.
• Initialize a global max_quality = values[0] (for the path just staying at 0).
• Initialize a frequency array visited_counts of size n, with visited_counts[0] = 1.
• Define a recursive function dfs(u, time_left, visited_counts, current_quality).
• In dfs(u, time_left, ...):
  • For each neighbor v of u with edge time t:
    • If time_left >= t:
      • Pruning Step: Check if time_left - t >= minTimeToZero[v]. If not, skip this path.
      • If the check passes, update visited_counts and new_quality.
      • If v == 0, update max_quality = max(max_quality, new_quality).
      • Make a recursive call: dfs(v, time_left - t, visited_counts, new_quality).
      • Backtrack by decrementing visited_counts[v].
• Start the search with dfs(0, maxTime, visited_counts, values[0]).
• Return max_quality.

The core idea is to avoid exploring futile paths. A path is futile if, from the current node, there isn't enough time left to return to node 0, even by taking the quickest possible route.

1. Preprocessing with Dijkstra's Algorithm: We first compute the shortest time from every node in the graph to node 0. Since the graph is undirected and times are non-negative, we can run Dijkstra's algorithm starting from node 0. The result is an array, minTimeToZero, where minTimeToZero[i] stores this minimum time for node i.

2. Optimized DFS with Pruning: We then perform a DFS, but with a much smarter recursive step. The state of our DFS is (u, timeLeft, visitedCounts, currentQuality).

When at a node u and considering a move to a neighbor v that takes time seconds:

• We first check if we have enough time for this single step: timeLeft >= time.
• Pruning: We then apply our key optimization. The time remaining after moving to v would be timeLeft - time. To complete a valid path, we must be able to get from v back to 0. The fastest this can be done is minTimeToZero[v]. Therefore, we must satisfy timeLeft - time >= minTimeToZero[v]. If this condition fails, we prune this entire branch of the search, as no path extending from v can be valid.

If the pruning check passes, we proceed with the recursive call, updating the currentQuality in O(1) time. Whenever a path reaches node 0, we treat it as a valid completed path and update our global maxQuality.

class Solution {
    int maxQuality = 0;
    List<int[]>[] adj;
    int[] values;
    int[] minTimeToZero;

    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        this.values = values;
        int n = values.length;
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
            adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }

        minTimeToZero = new int[n];
        Arrays.fill(minTimeToZero, Integer.MAX_VALUE);
        minTimeToZero[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{0, 0}); // {node, time}

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0];
            int time = curr[1];

            if (time > minTimeToZero[u]) {
                continue;
            }

            for (int[] neighbor : adj[u]) {
                int v = neighbor[0];
                int edgeTime = neighbor[1];
                if (minTimeToZero[u] + edgeTime < minTimeToZero[v]) {
                    minTimeToZero[v] = minTimeToZero[u] + edgeTime;
                    pq.offer(new int[]{v, minTimeToZero[v]});
                }
            }
        }

        int[] visitedCounts = new int[n];
        visitedCounts[0] = 1;
        this.maxQuality = values[0];
        dfs(0, maxTime, visitedCounts, values[0]);
        return this.maxQuality;
    }

    private void dfs(int u, int timeLeft, int[] visitedCounts, int currentQuality) {
        for (int[] neighbor : adj[u]) {
            int v = neighbor[0];
            int time = neighbor[1];

            if (timeLeft >= time) {
                int newTimeLeft = timeLeft - time;
                
                if (newTimeLeft >= minTimeToZero[v]) {
                    boolean isNewlyVisited = (visitedCounts[v] == 0);
                    visitedCounts[v]++;
                    
                    int newQuality = currentQuality + (isNewlyVisited ? values[v] : 0);
                    
                    if (v == 0) {
                        this.maxQuality = Math.max(this.maxQuality, newQuality);
                    }
                    
                    dfs(v, newTimeLeft, visitedCounts, newQuality);
                    
                    visitedCounts[v]--; // Backtrack
                }
            }
        }
    }
}