Minimum-Cost Round Trip Visiting Every City Once with Asymmetric Costs

A salesperson must visit n cities. The cost of traveling directly from city i to city j is dist[i][j], and every city can be reached directly from every other city. Starting from city 0, the salesperson must visit every other city exactly once and then return to city 0.

Return the minimum total cost of such a round trip.

Function Signature

def min_tour_cost(dist: list[list[int]]) -> int:

dist is an n x n matrix, and dist[i][j] is the cost of the direct leg from city i to city j.

Rules

• The cost of a round trip is the sum of dist[a][b] over its consecutive legs, including the final leg back to city 0.
• Costs may be asymmetric: dist[i][j] and dist[j][i] can differ, and each leg is charged in the direction it is traveled.
• City 0 is both the start and the end. Every other city is visited exactly once.
• If n == 1, the trip has no legs and costs 0.

Constraints

• 1 <= n <= 16
• len(dist) == n, and every row of dist has length n
• dist[i][i] == 0
• 0 <= dist[i][j] <= 10^6
• The answer is at most 1.6 * 10^7 and fits in a signed 32-bit integer.

Examples

Example 1

Input: dist = [[0, 3, 7, 4],
 [3, 0, 2, 6],
 [7, 2, 0, 5],
 [4, 6, 5, 0]]
Output: 14

The trip 0 → 1 → 2 → 3 → 0 costs 3 + 2 + 5 + 4 = 14, and so does its reverse. Every other round trip costs 19 or 21.

Example 2

Input: dist = [[0, 1, 10],
 [10, 0, 1],
 [1, 10, 0]]
Output: 3

The trip 0 → 1 → 2 → 0 costs 1 + 1 + 1 = 3. The opposite direction, 0 → 2 → 1 → 0, costs 10 + 10 + 10 = 30.

Example 3

Input: dist = [[0]]
Output: 0

With a single city there is nothing to travel.