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
|
Для отправки решений необходимо выполнить вход.
|