# Travelling Salesman

Problem #102

Tags: graphs classical puzzle

Who solved this?

The Travelling Salesman Problem, also known by abbreviation TSP has a very simple statement:

There is a Merchant (or Salesman) who wants to visit `N` cities (buying and selling goods there). The cities are connected by the network of roads of the known length. We want to find the path consisting of `N-1` roads and visiting all `N` cities, which have minimum possible length.

Though the statement is short, the solution could be not that easy to find and implement. To demonstrate this, we'll try to create program solving the TSP on a small network of `20` cities.

You should start from city `0` and finish anywhere you like, but all `20` cities should be visited, path should be the chain of `19` roads and its length should be minimal. All roads would be bi-directional, i.e. graph is "undirected".

Input data contains `20` lines, each describing roads from the given city.
Every line will start with the number of the city it is describing (just for convenience).
Then several pairs of numbers will follow in the form `T:L` where `T` is the target city of the given road and `L` is its length.
Answer should contain `20` values describing the path - simply the numbers of the cities visited in proper order.

Example (for simplicity with only `7` cities):

``````data:
0 1:90 2:42 3:90 5:29
1 0:90 3:98 2:70 4:65
2 0:42 1:70 5:30 3:36 4:97 6:46
3 1:98 2:36 0:90 5:77
4 1:65 2:97 6:68
5 2:30 3:77 0:29 6:90
6 5:90 2:46 4:68

The path length in this example is `321`.