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₀, c₁, …, c_m−1 ∈ {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 × n naturals que representen els costos x_ij (on 0 ≤ 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 ≤ k < m. Podeu suposar 1 ≤ n ≤ 10, 0 ≤ x_ij ≤ 10⁴, 0 ≤ m ≤ 10⁴, 0 ≤ 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.