We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Path Quality of a Graph

Difficulty: Hard

Problem Description

You are given an undirected graph with n nodes and an integer array values representing the value of each node. You need to determine the maximum quality of a valid path that starts and ends at node 0, takes at most maxTime seconds to complete, and the quality is the sum of the values of unique nodes visited.

Key Insights

  • A valid path must start and end at node 0.
  • The path can revisit nodes but should only count their values once for the quality.
  • The time taken for a path must not exceed maxTime.
  • The problem can be solved using backtracking or depth-first search (DFS) to explore all possible paths.

Space and Time Complexity

Time Complexity: O(2^E), where E is the number of edges, due to the potential exploration of all paths. Space Complexity: O(V + E), where V is the number of vertices, to store the graph representation and recursion stack.

Solution

To solve the problem, we can use a depth-first search (DFS) approach. We will represent the graph using an adjacency list, where each node points to its neighbors along with the travel time. The algorithm will recursively explore all paths starting from node 0, keeping track of the current time and the unique nodes visited. If the current path's time does not exceed maxTime, we calculate the quality and update the maximum quality if the current path's quality is higher.

Code Solutions

def maximumPathQuality(values, edges, maxTime):
    from collections import defaultdict
    
    # Build the graph as an adjacency list
    graph = defaultdict(list)
    for u, v, time in edges:
        graph[u].append((v, time))
        graph[v].append((u, time))
    
    n = len(values)
    max_quality = 0
    
    def dfs(node, time_remaining, visited):
        nonlocal max_quality
        if time_remaining < 0:
            return
        
        # Calculate current quality
        current_quality = sum(values[i] for i in visited)
        max_quality = max(max_quality, current_quality)
        
        # Explore neighbors
        for neighbor, travel_time in graph[node]:
            visited.add(neighbor)
            dfs(neighbor, time_remaining - travel_time, visited)
            visited.remove(neighbor)
    
    # Start DFS from node 0
    dfs(0, maxTime, {0})
    return max_quality
← Back to All Questions