Skip to main content
Talentd

Maximum Cost of Trip With K Highways - Solution & Explanation

HardPremiumFree on FleetCodeDynamic ProgrammingBit ManipulationGraphBitmask14 min read
Practice this problem

Problem Statement

A series of highways connect n cities numbered from 0 to n - 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli.

You are also given an integer k. You are going on a trip that crosses exactly k highways. You may start at any city, but you may only visit each city at most once during your trip.

Return the maximum cost of your trip. If there is no trip that meets the requirements, return -1.

 

Example 1:

Input: n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], k = 3
Output: 17
Explanation:
One possible trip is to go from 0 -> 1 -> 4 -> 3. The cost of this trip is 4 + 11 + 2 = 17.
Another possible trip is to go from 4 -> 1 -> 2 -> 3. The cost of this trip is 11 + 3 + 3 = 17.
It can be proven that 17 is the maximum possible cost of any valid trip.

Note that the trip 4 -> 1 -> 0 -> 1 is not allowed because you visit the city 1 twice.

Example 2:

Input: n = 4, highways = [[0,1,3],[2,3,2]], k = 2
Output: -1
Explanation: There are no valid trips of length 2, so return -1.

 

Constraints:

  • 2 <= n <= 15
  • 1 <= highways.length <= 50
  • highways[i].length == 3
  • 0 <= city1i, city2i <= n - 1
  • city1i != city2i
  • 0 <= tolli <= 100
  • 1 <= k <= 50
  • There are no duplicate highways.

Approach Overview

Problem Overview: You are given an undirected graph where cities are connected by highways with a cost. The goal is to choose a trip that uses exactly k highways and produces the maximum total cost, without revisiting cities in the same trip.

Approach 1: Backtracking / DFS Enumeration (Exponential Time)

Start a DFS from every city and explore all possible paths up to length k. Maintain a visited set so the same city is not used twice in a single path. At each step, iterate through neighboring cities and accumulate the highway cost. When the path length reaches k, update the global maximum. This approach explores nearly all permutations of length k, giving a time complexity around O(n * n^k) in dense graphs and O(k) recursion stack space. It works for very small graphs but quickly becomes infeasible as n grows.

Approach 2: State Compression Dynamic Programming (Bitmask DP) (O(2^n * n^2))

The constraint that cities cannot repeat suggests representing visited cities using a bitmask. Define dp[mask][u] as the maximum cost of a trip that visits the set of cities represented by mask and ends at city u. Iterate through all masks and attempt transitions to neighboring cities v that are not yet in the mask. If a highway u → v exists, update dp[mask | (1 << v)][v] with the accumulated cost.

The number of highways used equals bitcount(mask) - 1. Only states where the number of highways equals k are valid final trips. While iterating over states, expand paths until the mask size reaches k + 1 cities. Track the maximum cost among all valid states. Because each mask contains at most n cities and transitions check neighbors, the time complexity becomes O(2^n * n^2) with O(2^n * n) space.

This technique is called state compression because the visited set is encoded in an integer bitmask instead of a collection structure. It is commonly used in problems combining dynamic programming, bitmasking, and graph traversal.

Recommended for interviews: Interviewers expect the state compression DP solution. Brute force DFS demonstrates that you understand the path exploration aspect, but the optimal answer requires recognizing that the visited-city constraint fits naturally into a bitmask representation. Building dp[mask][node] and expanding states efficiently shows strong problem‑solving skills with graph DP.

Solution

We notice that the problem requires exactly k roads to be passed, and each city can only be visited once. The number of cities is n, so we can pass at most n - 1 roads. Therefore, if k \ge n, we cannot meet the requirements of the problem, and we can directly return -1.

In addition, we can also find that the number of cities n does not exceed 15, which suggests that we can consider using the method of state compression dynamic programming to solve this problem. We use a binary number of length n to represent the cities that have been passed, where the i-th bit is 1 indicates that the i-th city has been passed, and 0 indicates that the i-th city has not been passed yet.

We use f[i][j] to represent the maximum travel cost when the cities that have been passed are i and the last city passed is j. Initially, f[2^i][i]=0, and the rest f[i][j]=-infty.

Consider how f[i][j] transitions. For f[i], we enumerate all cities j. If the j-th bit of i is 1, then we can reach city j from other city h through the road, at this time the value of f[i][j] is the maximum value of f[i][h]+cost(h, j), where cost(h, j) represents the travel cost from city h to city j. Therefore, we can get the state transition equation:

$ f[i][j]=max_{h \in city}{f[i \backslash j][h]+cost(h, j)}

where i \backslash j represents changing the j-th bit of i to 0.

After calculating f[i][j], we judge whether the number of cities passed is k+1, that is, whether the number of 1s in the binary representation of i is k+1. If so, we update the answer as ans = max(ans, f[i][j]).

The time complexity is O(2^n times n^2), and the space complexity is O(2^n times n), where n$ represents the number of cities.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking / DFS Path EnumerationO(n * n^k)O(k)Small graphs or when exploring all paths conceptually before optimizing
State Compression Dynamic Programming (Bitmask DP)O(2^n * n^2)O(2^n * n)Optimal solution for n ≤ 15 graphs where cities cannot repeat

Video Solution

Maximum Subarray - Kadane's Algorithm -- Leetcode 53 • Greg Hogg • 367,056 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Cost of Trip With K Highways easy or hard?
Maximum Cost of Trip With K Highways is classified as Hard. The challenge comes from recognizing that the path constraint requires subset dynamic programming with bitmasking, a technique often used when the number of nodes is small but all combinations must be explored efficiently.
Maximum Cost of Trip With K Highways Python/Java solution
Python and Java implementations both follow the same idea: iterate through all bitmasks, track dp[mask][u], and transition to neighbors not yet visited. Bit operations like mask | (1 << v) update the visited set. The algorithm runs in O(2^n * n^2) regardless of language.
How to solve Maximum Cost of Trip With K Highways in O(2^n * n^2)?
Represent visited cities with a bitmask and use dynamic programming. Maintain dp[mask][u] as the maximum cost for visiting the cities in mask and ending at u. For each state, try extending the trip to an unvisited neighbor v if a highway exists. Only consider states where the number of edges used equals k when computing the final answer.
What is the best approach for Maximum Cost of Trip With K Highways?
The most effective solution uses state compression dynamic programming with a bitmask. The DP state dp[mask][u] stores the maximum trip cost for visiting the set of cities in mask and ending at city u. By expanding the mask to unvisited neighbors and counting edges using bitcount(mask) - 1, you compute the best path with exactly k highways. The complexity is O(2^n * n^2).
Is Maximum Cost of Trip With K Highways asked at Google/Amazon/Meta?
Graph path optimization combined with bitmask dynamic programming appears frequently in interviews at companies like Google, Amazon, and Meta. Variants include traveling with constraints, visiting subsets of nodes, or maximizing path value under length limits. This problem tests subset DP and graph traversal together.
What data structure is used in Maximum Cost of Trip With K Highways?
The solution relies on bitmasks to represent visited city sets and a 2D DP table dp[mask][node]. The graph itself is typically stored as an adjacency matrix or adjacency list for fast edge lookups during transitions.
What is the time complexity of Maximum Cost of Trip With K Highways?
The optimal bitmask DP solution runs in O(2^n * n^2) time and uses O(2^n * n) space. Each subset of cities (mask) is processed, and transitions check possible neighboring cities. Because n is small (typically ≤15), this state compression approach is efficient enough.

Ready to solve this problem?

Practice Maximum Cost of Trip With K Highways with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Reach City With Discounts

Next

Minimum Cost to Reach Destination in Time