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.