Prova - Pintant cotxes X64205

Una coneguda marca automobilística ens demana ajuda per millorar el procés de pintat dels seus cotxes. Els cotxes es pinten per tandes amb algun dels $n$ colors disponibles. Cada vegada que arriba un cotxe d’un color diferent del cotxe pintat just abans, cal netejar les pistoles. Aquesta tasca de neteja per passar del color $i$ al color $j$ té cost $x_{ij}$. Inicialment les pistoles ja estan netes i no hi ha cost. Quan finalment s’acaba la tanda de cotxes, cal tornar a netejar les pistoles, perquè estiguin llestes per quan arribi la tanda següent. Tanmateix aquesta neteja és especial, ja que si queden residus de pintura, es poden assecar i fer malbé les pistoles. Com que aquest últim procés té el mateix cost sigui quin sigui el darrer color usat, es pot excloure del càlcul de costos. Així doncs, només s’incorre en despesa quan hi ha un canvi de colors a la seqüència de cotxes.

Si una tanda consisteix en $m$ cotxes, cadascun identificat amb un natural $k$ entre $0$ i $m-1$, de colors $c_{0}$, $c_{1}$, …, $c_{m-1} \in \{0, 1, ..., n-1\}$ respectivament, quina és la forma òptima d’ordenar els cotxes per tal de minimitzar els costos de neteja?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un natural $n$, el nombre de colors disponibles. A continuació vénen $n \times n$ naturals que representen els costos $x_{ij}$ (on $0 \leq i, j < n$). Després ve $m$, el nombre de cotxes de la tanda. Finalment vénen els $m$ colors $c_{k}$ de cadascun dels cotxes, on $0 \leq k < m$. Podeu suposar $1 \leq n \leq 10$, $0 \leq x_{ij} \leq 10^{4}$, $0 \leq m \leq 10^{4}$, $0 \leq c_{k} < n$, i que per cada color $i$ tenim $x_{ii} = 0$ i hi ha almenys un cotxe $k$ tal que $c_{k} = i$.

Sortida

Escriviu la seqüència de cotxes lexicogràficament més petita entre les que tenen cost mínim, i el cost mínim.

Observació

Fer una cerca exhaustiva sobre totes les permutacions de cotxes serà massa lent.

Es valorarà la correctesa, l’eficiència, la completesa, la concisió, la llegibilitat i l’estructuració del programes enviats.