Practice/Meta/Leetcode 2247. Maximum Cost of Trip With K Highways

Leetcode 2247. Maximum Cost of Trip With K Highways

CodingOptional

Problem

You are given a weighted directed graph with n nodes numbered from 0 to n-1. Some edges in the graph are designated as "highways" while others are regular roads. Your task is to find the maximum total cost of a path from a start node to an end node, subject to the constraint that you can use at most k highways.

Each edge is represented as [from, to, cost, isHighway] where:

• from and to are node indices
• cost is the weight of the edge (positive integer)
• isHighway is 1 if the edge is a highway, 0 otherwise

You want to maximize the sum of edge costs along your path while respecting the highway limit. If no valid path exists that satisfies the constraint, return -1.

Requirements

1. Find a path from start to end that uses at most k highways
2. Among all valid paths, return the one with the maximum total cost
3. If multiple paths have the same maximum cost, any is acceptable
4. The graph may contain cycles, so track visited states carefully
5. Return -1 if no valid path exists

Constraints

• 2 <= n <= 50
• 1 <= edges.length <= 200
• 0 <= start, end < n
• start != end
• 0 <= k <= n
• 1 <= cost <= 1000
• isHighway is either 0 or 1
• The graph may have multiple edges between the same pair of nodes

Examples

Example 1:

Input: n = 5, edges = [[0,1,10,1],[1,2,20,0],[0,2,5,1],[2,3,15,0],[3,4,25,1]], start = 0, end = 4, k = 2 Output: 70 Explanation: The path 0→1→2→3→4 uses highways at edges [0,1] and [3,4] (exactly 2 highways). The total cost is 10+20+15+25 = 70. This is the maximum achievable.

Example 2:

Input: n = 3, edges = [[0,1,10,1],[1,2,20,1]], start = 0, end = 2, k = 1 Output: -1 Explanation: The only path from 0 to 2 is 0→1→2, which uses 2 highways. Since k = 1, this path violates the constraint.

Example 3:

Input: n = 4, edges = [[0,1,30,1],[1,3,40,1],[0,2,20,0],[2,3,50,0]], start = 0, end = 3, k = 1 Output: 70 Explanation: Path 0→2→3 uses 0 highways with total cost 70. Path 0→1→3 would give cost 70 but uses 2 highways (exceeds k=1).