Hamiltonian cycle of minimal cost P42934


Statement
 

pdf   zip

html

Given several directed graphs with n vertices, each one described with a matrix m of size n × n such that m[i][j] is the cost of going from vertex i to vertex j, calculate the minimum cost of the Hamiltonian cycles of every graph. A Hamiltonian cycle is a path that visits each vertex exactly once, and that ends at the starting vertex.

Input

Input consists of the description of several graphs. Each one begins with a natural number n ≥ 2, followed by the matrix n × n of costs (n lines, each with n natural numbers, with zeroes at the diagonal).

Output

Print the minimum cost of the Hamiltonian cycles of every graph.

Public test cases
  • Input

    3
    0 2 1
    2 0 4
    1 3 0
    4
    0 5 7 9
    2 0 2 2
    2 1 0 3
    2 9 9 0
    

    Output

    6
    12
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++