Since the triangular inequalities hold among the costs of traveling between the cities, so there is no need to travel from one city to another via other cities other than those two cities.

Searching all the orders of visiting towns requires a total of \(O(N! * N)\) time, in which the answer cannot be obtained in time under the constraints this time. The problem can be solved by the following DP:

\(DP[i][S]=\) The minimum cost when you are currently at city \(i\) and the set of towns you have already visited is \(S\)

\(DP[i][S]=\min\{DP[j][S\setminus \{i\}]+dist(i,j) \mid j\in S\setminus\{i\}\}\)

Here, you may hold the set \(S\) itself as a key, but you can treat those sets as integers by associating them with binaries, for example, Associating \(\{0,3,5\}\) with \(2^0+2^3+2^5=41\). That’s why this kind of DP is sometimes called bitDP.

The integer obtained by the correspondence, \(f(S)\), satisfies the following properties:

• \(i\in S \Longleftrightarrow\) The \(i\)-th bit of \(f(S)\) is \(1\)
• \(T \subset S \Longleftrightarrow (f(T) \text{ bitwiseor } f(S))=f(S) \Longrightarrow f(T) \leq f(S)\)

so operations and properties on sets can be represented concisely by bit operations.