Manies interpersonals P98089


Statement
 

pdf   zip

thehtml

Donades n persones i la mania que es tenen entre si, escolliu com fer-les seure en una taula allargada de manera que la suma de les manies interpersonals de les persones veïnes es minimitzi, amb una restricció: la persona aseguda més a l’esquerra ha de ser la primera persona donada.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguit de n noms diferents, seguit d’una matriu n × n de naturals entre 0 i 106, on la posició (i, j) conté la mania entre les persones i i j. La matriu és simètrica, amb zeros a la diagonal. Assumiu 1 ≤ n ≤ 12.

Sortida

Per a cada cas, escriviu la mínima suma de manies que es pot aconseguir, seguida de la disposició òptima de les persones a taula. Els jocs de proves són tals que sempre hi ha una única solució.

Public test cases
  • Input

    3
    anna maria nuria
    0 3 1
    3 0 9
    1 9 0
    
    1
    salvador
    0
    
    4
    a b c d
    0 1000 1000000 10
    1000 0 50000 30
    1000000 50000 0 7
    10 30 7 0
    

    Output

    10
    anna nuria maria
    0
    salvador
    1037
    a b d c
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Python