Optimal Travel Route

This problem asks you to compute the shortest route to visit all given cities exactly once and return to the starting city. Given n cities and a distance matrix where the entry at row i and column j denotes the distance from the i^th city to the j^th city, you are required to find the cyclic route that minimizes the total distance. Formally, given a set of cities \(\{c_1,c_2,\dots,c_n\}\) and a distance function \(d(c_i,c_j)\), find a permutation \(\pi\) of \(\{1,2,\dots,n\}\) that minimizes

[ \sum_{i=1}^{n-1} d(c_{\pi(i)}, c_{\pi(i+1)}) + d(c_{\pi(n)}, c_{\pi(1)}) ]

If there are no cities (i.e. \(n=0\)), simply output nothing. If there is a single city, the route should still start and end at that city.

inputFormat

The input is given through standard input (stdin) with the following format:

1. An integer \(n\) denoting the number of cities. \(0 \leq n \leq 10\).
2. If \(n > 0\), a line containing \(n\) space-separated strings representing the names of the cities.
3. If \(n > 0\), then \(n\) lines follow, each line contains \(n\) integers separated by spaces. The \(j^th\) integer in the \(i^th\) line represents the distance from the \(i^th\) city to the \(j^th\) city.

Note: The ordering of cities in the list corresponds to the order of rows in the distance matrix.

outputFormat

Output the optimal travel route as a single line to standard output (stdout). The route is a sequence of city names separated by a single space. The starting city should be repeated at the end to complete the cycle. If \(n = 0\), output an empty line.

4
A B C D
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

A B D C A