Camins hamiltonians P56416


Statement
 

pdf   zip

html

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 106.

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í.

Public test cases
  • Input

    3
    0 7 3
    9 0 2
    9 8 0
    

    Output

    1 2 3
    1 3 2
    min: 9
    
  • Input

    2
    0 1000000
    1 0
    

    Output

    1 2
    min: 1000000
    
  • Input

    5
    0 2 0 2 1
    0 0 2 0 2
    0 1 0 2 2
    0 2 1 0 2
    0 0 2 1 0
    

    Output

    1 2 3 4 5
    1 2 3 5 4
    1 2 5 3 4
    1 2 5 4 3
    1 4 2 3 5
    1 4 2 5 3
    1 4 3 2 5
    1 4 5 3 2
    1 5 3 4 2
    1 5 4 2 3
    1 5 4 3 2
    min: 4
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++