P2792 [JSOI2008] Small Shop Shopping

The members of the JSOI training team discovered that at their regular training site, there is a small shop that is very popular among nearby residents due to its rich variety of promotional deals, and business is booming.

The shop’s promotions are simple and fun: During a single shopping session, if you buy refined oil at this shop, then when you buy soap you can enjoy a discounted price of $2.00$ yuan per bar; if you buy soap, then when you buy cola you can enjoy a discounted price of $1.50$ yuan per can; and so on. In summary: if you buy item $A$, then you may buy item $B$ at a discounted price of $P$ yuan per unit (with no limit on the quantity). Interestingly, you need to buy some fixed items, and because different purchase orders may lead the shopkeeper to charge you different totals. For example, you need one bar of soap (original price $2.50$ yuan), one bottle of refined oil (original price $10.00$ yuan), and one can of cola (original price $1.80$ yuan). If you purchase in the order cola → refined oil → soap, the shopkeeper will charge you $13.80$ yuan; but if you purchase in the order refined oil → soap → cola, you only need to pay $13.50$ yuan. The local residents know that JSOI team members are good at programming, so they ask you to write a program: given the original prices of all items in the shop, all promotion rules, and the items you need, compute the minimum amount of money you must spend (you are not allowed to buy any unnecessary items, even if doing so could reduce the total cost).

The first line contains an integer $n\ (1 \le n \le 50)$, the total number of item types in the shop. The next $n$ lines follow. The $(i+1)$-th line contains a real number $c_i\ (0 < c_i \le 1000)$ and an integer $m_i\ (0 \le m_i \le 100)$ separated by a space, denoting the original price of item $i$ and the required quantity. The $(n+2)$-th line contains an integer $k\ (1 \le k \le 500)$, the total number of promotion rules. Then $k$ lines follow. Each line contains two integers $A, B\ (1 \le A, B \le n)$ and a real number $P\ (0 \le P < 1000)$, describing one promotion: if you buy item $A$, then you may buy item $B$ at a discounted price of $P$ yuan per unit. Here $P$ is less than the original price of item $B$. All pairs $(A, B)$ in the promotions are distinct. For convenience, the shopkeeper does not use one-cent units, so all prices are multiples of $0.10$ yuan.

Output a single real number: the minimum total cost. Print the number with exactly two decimal places.

Constraints can be found in the Input Format. Translated by ChatGPT 5