The Shortest Tour of Every City
n cities are given by a full cost matrix: c[i][j] is the cost of travelling from city i
to city j, and it need not equal c[j][i].
Start at city 1, visit every other city exactly once, and return to city 1. Print the smallest total cost.
4 cities, matrix rows 0 10 15 20 / 10 0 35 25 / 15 35 0 30 / 20 25 30 0 -> 80
1 city -> 0
## Why the state must be a set
Standing in city u partway through, the cheapest way to finish depends on exactly WHICH
cities remain. Two routes that have visited the same number of cities but different ones face
completely different remainders, so a counter is not enough.
There is no smaller summary available. That is the honest answer, and it is why this problem is exponential rather than polynomial.
## The state
dp[mask][u] = cheapest way to start at city 0, visit exactly the cities in mask, and stop at u
with u required to be in mask, and bit 0 always set because the tour begins there.
dp[1][0] = 0
dp[mask | (1<<v)][v] = min over u in mask of dp[mask][u] + c[u][v]
answer = min over u of dp[full][u] + c[u][0]
## The position is part of the state
Dropping u and keeping only dp[mask] does not work, because the cost of the next hop
depends on where you are standing. A set alone says what has been done, not where it left you.
Problem 583 is the version where the position IS determined by the mask, and comparing the two is the cleanest way to see what this second index is buying.
## The fill order is free
Every transition sets one more bit, so it moves from mask to a strictly LARGER mask. Looping
mask from 0 upwards therefore reads only entries already written. No sorting and no
recursion are needed, which is the practical reason bitmask tables are usually written as
plain loops.
## Cost
Time O(2^n * n^2). Space O(2^n * n).
At n = 15 that is about 7 million steps and half a million table entries.
## Boundaries
One city answers 0: there is nowhere to go.
Two cities answer c[0][1] + c[1][0], which the asymmetric tests check is not being halved.