Taco Traveling Salesman Problem

You are given a set of cities and the pairwise distances between them. Your task is to determine the shortest possible route that starts at the first city, visits every other city exactly once, and returns to the starting city.

The distance between any two cities is provided in an n × n matrix. You must output the order of city names representing the optimal route.

The mathematical formulation of the total route distance is given by:

\( \text{Total Distance} = d_{a_0,a_1} + d_{a_1,a_2} + \cdots + d_{a_{n-1},a_0} \)

where \(a_0, a_1, \dots, a_{n-1}\) is a permutation of city indices with \(a_0\) fixed as the starting city.

inputFormat

The input is read from stdin and has the following format:

1. An integer n representing the number of cities.
2. A single line with n city names separated by spaces.
3. n lines follow, each containing n integers. The j-th integer on the i-th line represents the distance \(d_{i,j}\) between the i-th and j-th city.

outputFormat

Output to stdout a single line containing the order of city names (separated by a single space) that represents the shortest round-trip route starting and ending at the first city.

2
A B
0 10
10 0

A B A