Minimum-Cost Round Trip Visiting Every City Once with Asymmetric Costs
Company: Goldman Sachs
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: dist = [[0]]
Output: 0
```
With a single city there is nothing to travel.
Overview: Given a complete matrix of possibly asymmetric travel costs between up to 16 cities, return the minimum cost of a round trip that starts at city 0, visits every other city exactly once and returns to city 0. The problem tests exact optimization over subsets of cities within tight limits.
Read the full Goldman Sachs Quantitative Researcher interview experience this question came from
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`.
Implement `min_tour_cost(dist)`, which returns the minimum total cost of such a round trip.
`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`.
- Only the minimum cost is returned, so when several round trips tie, the answer is that shared cost.
### 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. No value exceeds `2^31 - 1`, so Java and C++ return `int`.
### Example 1
```text
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
```text
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.
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
Input: ([[0]],)
Expected Output: 0
Explanation: Minimum valid, n = 1: a single city has no legs, so the round trip costs 0.
Input: ([[0, 5], [9, 0]],)
Expected Output: 14
Explanation: n = 2 with asymmetric costs: the only round trip 0 -> 1 -> 0 costs dist[0][1] + dist[1][0] = 5 + 9 = 14.
Hints
- Each leg is charged in the direction it is traveled, and the final leg back to city 0 is part of the cost.
- Costs need not obey the triangle inequality, so a cheap first leg can force expensive legs later; judge complete round trips, not individual legs.
- Only the minimum cost is returned, so when several round trips tie, they all give the same answer.