Cicle Hamiltonià de cost mínim P42934

Donats diversos grafs dirigits amb $n$ vèrtexos, cadascun descrit amb una matriu $m$ de mida $n \times 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 \ge 2$, seguit de la matriu $n \times 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.