Camins hamiltonians P56416

Donat un graf dirigit amb costs positius als arcs, escriviu tots els camins que surten del primer vèrtex i passen per tots els vèrtexs exactament un cop. A més, calculeu el cost mínim de tots aquests camins.

Entrada

L’entrada consisteix en el nombre de vèrtexs n, seguit de n files amb n naturals 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. Un cost igual a zero indica que l’arc no existeix (la diagonal només té zeros). Suposeu 2 ≤ n ≤ 15, i que tots els costs estan entre 1 i 10⁶.

Sortida

Escriviu, en ordre lexicogràfic, tots els camins que surten del primer vèrtex i passen per tots els vèrtexs exactament un cop. Al final, escriviu el cost mínim de tots aquests camins. Sempre hi haurà almenys un camí.