HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50691 - The traveling salesman problem

Guest
• Discussion of problem (1)

Section problems

• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres
• 50691 - The traveling salesman...
• 50701 - Cell Removal
• 50703 - The Shortest Path
• 50704 - Connected?
• 50705 - Student Clubs

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Difficulty Gamma

The traveling salesman problem

Russian
A graph without loops and multiple edges, all edges have weight, expressed natural number. Required in this graph to find the path passing over all vertices (and each - exactly one), and at the end returning to the initial vertex, and the total weight of all edges in this path should be minimal.

Input
At the entrance is written first, the number of N (3 ≤ N ≤ 9). Then is the adjacency matrix ( N * N numbers), the number of i -th row j -th column describes an edge between vertices i and j : if an edge exists, then this number is equal to its weight, if edge does not exist, then recorded the number 0.
Undirected graph, ie, the matrix is symmetric with respect to the main diagonal, on the main diagonal are zeros.
Weight of each edge is given a natural number from 1 to 1000.
Output
Derive N plus one number - found a way (the first and last of its vertices must match). It is guaranteed that there is always a way.

Input
4
0 0 10 20
0 0 3 10
10 3 0 2
20 10 2 0
Output
1 3 2 4 1

Для отправки решений необходимо выполнить вход.

www.contester.ru