Cicle Hamiltonià de cost mínim P42934


Statement
 

pdf   zip

thehtml

Donats diversos grafs dirigits amb n vèrtexos, cadascun descrit amb una matriu m de mida n × n tal que m[i][j] és el cost d’anar del vèrtex i al vèrtex j, calculeu el cost mínim dels cicles Hamiltonians de cada graf. Un cicle Hamiltonià és un camí que visita exactament un cop cada vèrtex, i que acaba a l’origen.

Entrada

L’entrada consisteix en la descripció de diversos grafs. Cadascuna comença amb un natural n ≥ 2, seguit de la matriu n × n de costos (n línies, cadascuna amb n naturals, amb la diagonal a zero).

Sortida

Escriviu el cost mínim dels cicles Hamiltonians de cada graf.

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
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python