主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 D: A Shopping Problems

问题 D: A Shopping Problems

时间限制: 1 Sec  内存限制: 256 MB
提交: 22  解决: 2
[提交][状态][讨论版]

题目描述

V8发现,在实验室楼下,小苹果因为其丰富的经营优惠方案深受同学的青睐,生意十分红火。因其经营优惠方案十分简单有趣:

一次消费过程中,如您在本店购买了绿茶,购买香肠时就可以享受 2.00 元/根的优惠价; 如果您在本店购买了香肠,您购买可乐就可以享受 1.50 元/听的优惠价;……,诸如此类的优惠方案就是说:如您在本店购买了商品 A,您就可以以 P 元/件的优惠价购买商品 B(购买的数量不限)。 有趣的是,你需要购买同样一些商品,由于不同的购买顺序,老板可能会叫你付不同数量的钱。比如,您需要一根香肠(原价 2.50 元/根)、一瓶绿茶(原价 10.00 元/瓶)、一听可乐(原价 1.80 元/听),如果你按照可乐、绿茶、香肠这样的顺序购买,老板会问你要 13.80 元;而如果你按照绿茶、香肠、可乐这样的顺序购买,你只需付 13.50 元。 V8于是请大家编写一个程序:在告诉商品的原价,所有的优惠方案及所需的商品后,计算至少需要花费多少钱(不允许购买任何不需要的商品,即使这样做可能使花费的钱更少)。 1.可能有自己优惠自己的,即第二个开始就可以优惠了 2.而且可以先只买某种物品的一个,再通过其他的优惠使得该类物品剩下的享受优惠.

输入

输入第一行为一个整数 n(1<=n<=50),表示小店的商品种数。

接下来是 n 行,其中第(i+1)行由一个实数 Ci(0<Ci<=1000)和一个整数 Mi(0<=Mi<=100)组成,其间由一个空格分隔,分别表示第 i 种商品的原价和所需的数量。 第(n+2)行又是一个整数 K,表示小店的优惠方案总数。

然后是一个整数K(1<=K<=500)

接下来 K 行,每行有两个整数 A,B(1<=A,B<=n)和一个实数 P(0<=P<1000),表示一种优 惠方案,即如果您购买了商品 A,您就可以以 P 元/件的优惠价购买商品 B,P 小于商品 B 的 原价。所有优惠方案的(A,B)都是不同的。为了方便老板不收分币,所以所有价格不出现单位分。

输出

输出只有一个实数,表示最少需要花多。输出实数须保留两位小数。

样例输入

4
10.00 1
1.80 1
3.00 0
2.50 2
2
1 4 2.00
4 2 1.50

样例输出

15.50

提示

[提交][状态][讨论版]