Vacances P64430

Enguany fareu una ruta pels Estats Units, i decidiu emportar-vos 1000$ en metàl·lic. Quan aneu a l’oficina de canvi, trobeu que cada 1$ costa 0.93€. De manera que, en principi, hauríeu de gastar-vos 930€. Però veieu que cada 1$ costa 0.79£, i que cada 1£ costa 1.17€. Astutament se us acut que, si feu servir lliures esterlines com a moneda intermitja, podeu aconseguir un tracte millor que fent el canvi directe d’euros a dòlars: els 1000$ costen 790£, que costen $790 \times 1.17 = 924.30$€, i així aconseguiu un modest estalvi de 5.70€.

Feu un programa que us ajudi a estalviar-vos diners.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de monedes $n$ de l’oficina de canvi. A continuació ve una matriu $n \times n$ amb uns a la diagonal, on el coeficient $m_{ij} > 0$ a la fila $i$ i columna $j$ és un real que representa el cost de $1$ unitat de la moneda $i$ en la moneda $j$. A continuació ve el nombre de preguntes $q > 0$. Finalment vénen $q$ preguntes, cadascuna consistent en dos enters $i$ i $j$ (diferents, ambdós entre 0 i $n-1$), i un nombre real $x > 0$, el nombre d’unitats de la moneda $i$ que voleu comprar amb la moneda $j$.

Suposeu $2 \le n \le 80$ i que, per als jocs de proves grossos, $q = \Theta(n^3)$. També podeu assumir que, per a tot cicle que comença i acaba en la moneda $i$, el cost de convertir 1 unitat de la moneda $i$ en moneda $i$ seguint el cicle és almenys de 1 unitat de la moneda $i$ (altrament, l’oficina de canvi ja hauria tancat per fallida).

Sortida

Per a cada pregunta consistent en $x$, $i$, $j$, escriviu el cost mínim de comprar $x$ unitats de la moneda $i$ en la moneda $j$, amb dues xifres decimals. Per fer-ho, poseu aquestes dues línies al principi del vostre main:

    cout.setf(ios::fixed);
    cout.precision(2);

Escriviu una línia amb 10 guions després de cada cas. Els jocs de proves no tenen problemes de precisió.