Funcia
Lv.4bitmaskdp

Traveling Salesman (Bitmask DP)

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

cost[i][j] is the (possibly asymmetric) cost from city i to city j. Starting at city 0, visit every other city exactly once and return to 0; return the minimum total cost.

Examples

costresult
[[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]35
[[0, 3], [7, 0]]10

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(cost: int[][]) → int

Constraints

  • 2≤n≤142 \le n \le 14; cost[i][i] = 0, otherwise 1≤1 \le cost[i][j] ≤106\le 10^6

Expected complexity

Time
O(2^N * N^2)
Space
O(2^N * N)

Examples

costExpected
[[0,10,15,20],[5,0,9,10],[6,13,0,12],[8,8,9,0]]35
[[0,3],[7,0]]10

Hint

Hint

Bitmask DP over (visited set, current city): dp[1][0] = 0, extend to unvisited w, answer min dp[full][v] + cost[v][0]; O(2nn2)O(2^n n^2). Trying all (n−1)!(n-1)! orders exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness407verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.