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 <= 151 <= highways.length <= 50highways[i].length == 30 <= city1i, city2i <= n - 1city1i != city2i0 <= tolli <= 1001 <= k <= 50Problem 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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking / DFS Path Enumeration | O(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 |
Maximum Subarray - Kadane's Algorithm -- Leetcode 53 • Greg Hogg • 367,056 views views
Watch 9 more video solutions →Practice Maximum Cost of Trip With K Highways with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor