LeetCode 2247 - Maximum Cost of Trip With K Highways

LeetCode Problem 2247

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Bit Manipulation, Graph Theory, Bitmask

Solution

Problem Understanding

The problem gives us an undirected weighted graph with n cities and a list of highways. Each highway connects two cities and has an associated toll cost. We must find the maximum possible total toll for a trip that uses exactly k highways.

There are two important restrictions:

1. We may start from any city.
2. Each city can be visited at most once.

The second condition means the trip must be a simple path, not a walk with repeated vertices. Since traversing exactly k highways means the trip contains exactly k + 1 distinct cities, we are effectively searching for the maximum weight simple path of length k.

The input consists of:

• n, the number of cities
• highways, where each entry [u, v, w] means there is an undirected edge between u and v with weight w
• k, the exact number of edges that must be traversed

The output is:

• The maximum possible total toll among all valid paths using exactly k highways
• -1 if no such path exists

The constraints are the most important clue for choosing the algorithm:

• n <= 15
• highways.length <= 50
• k <= 50

The small value of n immediately suggests that exponential algorithms involving subsets or bitmasks are feasible. Since 2^15 = 32768, dynamic programming over subsets becomes practical.

At the same time, k can be as large as 50, which is much larger than n - 1. Because we cannot revisit cities, the longest possible valid path contains at most n - 1 edges. Therefore:

• If k >= n, the answer is automatically -1

Several edge cases are important:

• The graph may be disconnected.
• There may be no path containing exactly k edges.
• The optimal path may start from any city.
• Some edges may have zero cost.
• Since cities cannot repeat, cycles are forbidden even if they would increase the cost.

A naive DFS that explores all simple paths quickly becomes too slow because the number of possible simple paths grows exponentially.

Approaches

Brute Force Approach

The most direct solution is to try every possible simple path using depth first search.

We can start DFS from every city. During the search:

• Keep track of visited cities
• Track how many highways have been used
• Accumulate the current toll cost
• Update the global maximum whenever exactly k highways are used

This approach is correct because it explicitly enumerates every valid simple path of length k.

However, the complexity is extremely high. In the worst case, the graph is dense and every recursive call may branch into many unvisited neighbors. The number of simple paths grows roughly factorially.

For n = 15, this becomes impractical.

Optimal Approach, Bitmask Dynamic Programming

The key observation is that n is very small.

Whenever we see n <= 15, subset dynamic programming becomes a strong candidate. Since we cannot revisit cities, the set of visited cities completely characterizes an important part of the state.

We define a DP state based on:

• Which cities have already been visited
• Which city we are currently at

Specifically:

• dp[mask][u] represents the maximum toll cost of a path that:

• visits exactly the cities in mask

• ends at city u

Each bit in mask indicates whether a city has been visited.

From a state (mask, u), we try extending the path to every unvisited neighbor v.

This works because:

• The no-revisit condition is naturally enforced by the bitmask

• Every valid simple path corresponds to exactly one sequence of transitions

• The number of states is manageable:

• 2^15 * 15 ≈ 500,000

We only care about masks whose number of set bits equals k + 1, since a path with k edges contains k + 1 cities.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Enumerates all simple paths
Optimal	O(2^n * n^2)	O(2^n * n)	Bitmask DP over visited cities

Algorithm Walkthrough

Step 1, Build the Graph

Convert the highway list into an adjacency list.

For every highway [u, v, w]:

• Add (v, w) to u
• Add (u, w) to v

Since the graph is undirected, both directions must exist.

Step 2, Handle Impossible Cases Early

A valid path with k highways requires k + 1 distinct cities.

Since there are only n cities:

• If k >= n, return -1

No valid simple path can exist.

Step 3, Define the DP State

We create:

dp[mask][u]

This stores the maximum cost of a path:

• Visiting exactly the cities in mask
• Ending at city u

If a state is unreachable, store -1.

The mask is a binary number:

• Bit i is 1 if city i has been visited

Example:

mask = 10101

means cities 0, 2, and 4 are visited.

Step 4, Initialize Single-City Paths

Every city can be a starting point.

For each city i:

dp[1 << i][i] = 0

A path containing only one city has cost 0.

Step 5, Transition Between States

For every state (mask, u):

• Try every neighbor (v, w) of u

• If v is already visited, skip it

• Otherwise:

• Create:

new_mask = mask | (1 << v)

• Update:

dp[new_mask][v] =
    max(dp[new_mask][v], dp[mask][u] + w)

This extends the current path by one edge.

Step 6, Extract the Answer

A path with exactly k highways contains exactly k + 1 cities.

Therefore:

• Iterate over all masks
• Only consider masks with k + 1 set bits
• Check every ending city

The maximum value among these states is the answer.

If no valid state exists, return -1.

Why it works

The DP state fully captures all information needed to continue building a valid path:

• The visited set guarantees no city is revisited
• The ending city determines which edges may be taken next

Every simple path corresponds to exactly one sequence of DP transitions, and every DP transition produces a valid simple path. Since we maximize the total cost during transitions, the final answer is the maximum possible toll among all valid paths of length k.

Python Solution

from typing import List

class Solution:
    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:
        if k >= n:
            return -1

        graph = [[] for _ in range(n)]

        for u, v, w in highways:
            graph[u].append((v, w))
            graph[v].append((u, w))

        size = 1 << n

        dp = [[-1] * n for _ in range(size)]

        for city in range(n):
            dp[1 << city][city] = 0

        for mask in range(size):
            for u in range(n):
                if dp[mask][u] == -1:
                    continue

                for v, w in graph[u]:
                    if mask & (1 << v):
                        continue

                    new_mask = mask | (1 << v)

                    dp[new_mask][v] = max(
                        dp[new_mask][v],
                        dp[mask][u] + w
                    )

        answer = -1

        for mask in range(size):
            if mask.bit_count() != k + 1:
                continue

            for city in range(n):
                answer = max(answer, dp[mask][city])

        return answer

The implementation begins by handling the impossible case where k >= n. Since we cannot revisit cities, a path longer than n - 1 edges cannot exist.

Next, the graph is converted into an adjacency list. This allows efficient traversal of neighboring cities during DP transitions.

The DP table is initialized with -1, meaning unreachable states. Each city is then initialized as a starting point with cost 0.

The main nested loops iterate over all subset masks and ending cities. Whenever a reachable state is found, the algorithm tries extending the path to every unvisited neighbor.

The transition step updates the best known cost for the new state.

Finally, the algorithm scans all masks containing exactly k + 1 cities. Since a path with k edges must contain k + 1 distinct vertices, these are exactly the valid final states.

Go Solution

package main

import (
	"math/bits"
)

func maximumCost(n int, highways [][]int, k int) int {
	if k >= n {
		return -1
	}

	type Edge struct {
		to   int
		cost int
	}

	graph := make([][]Edge, n)

	for _, h := range highways {
		u, v, w := h[0], h[1], h[2]

		graph[u] = append(graph[u], Edge{v, w})
		graph[v] = append(graph[v], Edge{u, w})
	}

	size := 1 << n

	dp := make([][]int, size)

	for i := range dp {
		dp[i] = make([]int, n)

		for j := range dp[i] {
			dp[i][j] = -1
		}
	}

	for city := 0; city < n; city++ {
		dp[1<<city][city] = 0
	}

	for mask := 0; mask < size; mask++ {
		for u := 0; u < n; u++ {
			if dp[mask][u] == -1 {
				continue
			}

			for _, edge := range graph[u] {
				v := edge.to
				w := edge.cost

				if (mask & (1 << v)) != 0 {
					continue
				}

				newMask := mask | (1 << v)

				if dp[mask][u]+w > dp[newMask][v] {
					dp[newMask][v] = dp[mask][u] + w
				}
			}
		}
	}

	answer := -1

	for mask := 0; mask < size; mask++ {
		if bits.OnesCount(uint(mask)) != k+1 {
			continue
		}

		for city := 0; city < n; city++ {
			if dp[mask][city] > answer {
				answer = dp[mask][city]
			}
		}
	}

	return answer
}

The Go implementation follows the same DP logic as the Python version.

A custom Edge struct is used for adjacency lists. The DP table is initialized manually because Go slices default to 0, while unreachable states require -1.

The math/bits package provides bits.OnesCount, which efficiently counts the number of set bits in a mask.

Integer overflow is not a concern because the maximum total toll is small:

Maximum cost <= 14 * 100 = 1400

Worked Examples

Example 1

n = 5
highways = [
    [0,1,4],
    [2,1,3],
    [1,4,11],
    [3,2,3],
    [3,4,2]
]
k = 3

Graph

0 --4-- 1 --11-- 4
        |
        3
        |
        2 --3-- 3 --2-- 4

We need paths using exactly 3 edges, meaning 4 cities.

Initial States

Mask	Ending City	Cost
00001	0	0
00010	1	0
00100	2	0
01000	3	0
10000	4	0

Important Transitions

Start from city 0.

Current State	Transition	New State	Cost
(00001, 0)	0 -> 1	(00011, 1)	4
(00011, 1)	1 -> 4	(10011, 4)	15
(10011, 4)	4 -> 3	(11011, 3)	17

Mask 11011 contains 4 cities, so it represents a valid path with 3 highways.

The maximum cost found is:

17

Example 2

n = 4
highways = [
    [0,1,3],
    [2,3,2]
]
k = 2

We need paths using exactly 2 edges, meaning 3 cities.

However:

• Component {0,1} contains only one edge
• Component {2,3} contains only one edge

No simple path with 2 edges exists.

All DP states with 3 visited cities remain unreachable.

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n * n^2)	Every subset and ending city may transition to multiple neighbors
Space	O(2^n * n)	DP table stores one value per (mask, city) state

The number of masks is 2^n, and for each mask we process up to n ending cities. Each transition explores neighboring vertices. Since the graph has at most 50 edges, the practical runtime is very manageable for n <= 15.

The memory usage is also feasible because:

2^15 * 15 ≈ 500,000 states

which comfortably fits within typical limits.

Test Cases

from typing import List

class Solution:
    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:
        if k >= n:
            return -1

        graph = [[] for _ in range(n)]

        for u, v, w in highways:
            graph[u].append((v, w))
            graph[v].append((u, w))

        size = 1 << n

        dp = [[-1] * n for _ in range(size)]

        for city in range(n):
            dp[1 << city][city] = 0

        for mask in range(size):
            for u in range(n):
                if dp[mask][u] == -1:
                    continue

                for v, w in graph[u]:
                    if mask & (1 << v):
                        continue

                    new_mask = mask | (1 << v)

                    dp[new_mask][v] = max(
                        dp[new_mask][v],
                        dp[mask][u] + w
                    )

        answer = -1

        for mask in range(size):
            if mask.bit_count() != k + 1:
                continue

            for city in range(n):
                answer = max(answer, dp[mask][city])

        return answer

sol = Solution()

assert sol.maximumCost(
    5,
    [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]],
    3
) == 17  # official example 1

assert sol.maximumCost(
    4,
    [[0,1,3],[2,3,2]],
    2
) == -1  # official example 2

assert sol.maximumCost(
    2,
    [[0,1,5]],
    1
) == 5  # smallest valid graph

assert sol.maximumCost(
    3,
    [[0,1,5],[1,2,7]],
    2
) == 12  # simple chain

assert sol.maximumCost(
    3,
    [[0,1,5],[1,2,7]],
    3
) == -1  # impossible because k >= n

assert sol.maximumCost(
    4,
    [[0,1,1],[1,2,2],[2,3,3],[0,3,100]],
    2
) == 102  # best path is 1->0->3

assert sol.maximumCost(
    5,
    [[0,1,0],[1,2,0],[2,3,0],[3,4,0]],
    4
) == 0  # all zero-cost edges

assert sol.maximumCost(
    5,
    [[0,1,1],[1,2,1],[2,3,1],[3,4,1],[0,4,10]],
    1
) == 10  # best single edge

assert sol.maximumCost(
    5,
    [[0,1,1],[1,2,10],[2,3,10],[3,4,10]],
    3
) == 30  # best long path

assert sol.maximumCost(
    6,
    [[0,1,5],[1,2,6],[2,3,7],[3,4,8],[4,5,9]],
    5
) == 35  # uses every city exactly once

Test Summary

Test	Why
Official example 1	Verifies standard successful case
Official example 2	Verifies disconnected graph handling
Smallest valid graph	Tests minimum input size
Simple chain	Tests straightforward path accumulation
k >= n	Tests impossible condition
Expensive shortcut	Ensures algorithm finds optimal path
Zero-cost edges	Ensures zero weights are handled correctly
Best single edge	Tests k = 1
Long optimal path	Tests deeper DP transitions
Full graph traversal	Tests maximum simple path length

Edge Cases

One important edge case occurs when k >= n. Since a valid trip cannot revisit cities, a path with k edges requires k + 1 distinct cities. If there are not enough cities available, the answer must be -1. The implementation handles this immediately with an early return, avoiding unnecessary DP computation.

Another tricky case is a disconnected graph. A naive implementation might incorrectly assume some path always exists if enough edges are present globally. However, the required path may span more cities than any connected component contains. The DP naturally handles this because unreachable states remain -1.

A third important case involves cycles. Since revisiting cities is forbidden, the algorithm must never allow transitions back into already visited nodes. The bitmask check:

if mask & (1 << v):
    continue

guarantees every path remains simple.

Zero-cost edges are also important. Some implementations incorrectly use 0 to mean "unreachable." This solution uses -1 for unreachable states, so valid paths with total cost 0 are handled correctly.