Cicle Hamiltonià de cost mínim P42934

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.