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 × 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 × 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 ≤ n ≤ 80 i que, per als jocs de proves grossos, q = Θ(n³). 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ó.