Tots els cicles hamiltonians P16553

Donat un graf dirigit amb costs positius als arcs, escriviu tots els camins que surten del primer vèrtex, acaben al primer vèrtex, i passen per tots els altres vèrtexs exactament un cop. A més, escriviu el cost de cadascun d’aquests cicles.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs $n$, seguit de $n$ files amb $n$ nombres cadascuna. El nombre $j$-èsim de la fila $i$-èsima indica el cost de l’arc que va del vèrtex $i$ al vèrtex $j$ (els vèrtexs es numeren de 0 a $n - 1$). Un cost igual a zero indica que l’arc no existeix (la diagonal només té zeros). Poseu suposar que $n$ és “petita” i com a mínim 2, i que el cost de cada cicle cap en un enter.

Sortida

Escriviu, en ordre lexicogràfic, tots els cicles de longitud $n$ que surten i acaben en el vèrtex 0 sense repetir vèrtexs, i el cost de cada cicle. Escriviu una línia amb 20 guions al final de cada cas.