Hamiltonian paths P56416


Statement
 

pdf   zip

html

Given a directed graph with arcs with positive costs, print all the paths that begin at the first vertex and visit all vertices exactly once. Moreover, compute the minimum of the costs of these paths.

Input

Input consists of the number of vertices n, followed by n rows with n natural numbers each. The j-th number of the i-th row indicates the cost of the arc going from vertex i to vertex j. A zero cost indicates a missing arc (the diagonal has only zeros). Assume 2 ≤ n ≤ 15, and that all costs are between 1 and 106.

Output

Print, in lexicographical order, print all the paths that begin at the first vertex and visit all vertices exactly once. Afterwards, print the minimum cost of all these paths. There will always be at least one path.

Public test cases
  • Input

    3
    0 7 3
    9 0 2
    9 8 0
    

    Output

    1 2 3
    1 3 2
    min: 9
    
  • Input

    2
    0 1000000
    1 0
    

    Output

    1 2
    min: 1000000
    
  • Input

    5
    0 2 0 2 1
    0 0 2 0 2
    0 1 0 2 2
    0 2 1 0 2
    0 0 2 1 0
    

    Output

    1 2 3 4 5
    1 2 3 5 4
    1 2 5 3 4
    1 2 5 4 3
    1 4 2 3 5
    1 4 2 5 3
    1 4 3 2 5
    1 4 5 3 2
    1 5 3 4 2
    1 5 4 2 3
    1 5 4 3 2
    min: 4
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++