Manies interpersonals P98089

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 \times n$ de naturals entre 0 i $10^6$, 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 \le n \le 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ó.