Maximum Path Quality of a Graph · Interview Problem

Back to problems

Leetcode

maximum-path-quality-of-a-graph

Medium

Graphs

Backtracking

Bit Manipulation

Depth-First Search

Maximum Path Quality of a Graph

Find the maximum path quality of a graph where the path starts and ends at node 0.

Acceptance 100%

Start Practice

Problem Statement

Core description from the backend problem record.

Description

You are given a graph with n nodes (0 to n-1) and edges where each node has a value. The graph is undirected and weighted by travel time. You start at node 0 and can travel edges with a total travel time at most maxTime. The quality of a path is the sum of the values of the unique nodes visited in that path. Return the maximum path quality of any path starting and ending at node 0 within the given maxTime.

Input Format

n: integer, number of nodes
values: integer array of length n, values of each node
edges: integer 2D array where each edge is [u, v, time] representing an undirected edge between u and v with travel time
maxTime: integer, maximum total travel time allowed

Output Format

Integer representing the maximum path quality achievable

Constraints

1 <= n <= 1000
0 <= values[i] <= 10^8
0 <= u, v < n
1 <= time <= 1000
1 <= maxTime <= 10^9
0 <= edges.length <= 3000

Loading Preptin

Description

Input Format

Output Format

Constraints