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

问题 C: 梦想庄园

时间限制: 1 Sec  内存限制: 128 MB
提交: 392  解决: 108
[提交][状态][讨论版]

题目描述

        亮亮最近在玩一款叫做“梦想庄园”的经营游戏。在游戏中,你可以耕种,养羊甚至建造纺织厂。
如果你需要制造衣服,你首先得有布匹和毛线。布匹由棉花纺织而成;毛线由羊毛制成,而羊需要饲料才能长出羊毛,最终饲料由小麦和胡萝卜制成。
        假设游戏中共有N种物品,第i种物品由其他Ci个物品制成。亮亮需要你帮他制作M个任务物品来完成销售订单。
        一开始,亮亮会给你K个物品作为原材料,你可以使用这些物品来制作需要的M个任务物品。
        游戏中的每个物品都有一个价格Vi,当原材料不足以制作出所有的物品时,你需要花尽量少的钱买一些物品来完成任务。你可以选择直接购买所需的任务物品,也可以购买其他物品来制作任务物品,但是每制作一次需要W的代价。

输入

第一行,一个整数T代表测试数据组数。
接下来一行,三个整数代表N,M,W。
 其中0<= N <= 10000, 0 <= M <= N。
接下来N行,第i行(从0开始计数)开始两个整数分别为Vi(0<= Vi <= 10000), Ci(0 <= Ci <= N)。接下来Ci个整数,代表第i个物品由哪些物品来制成。(数据保证没有环,即不存在某一物品经过一系列依赖关系依赖自己
接下来一行M个整数,代表M个任务物品。
输入保证答案不超过int的表示范围。

输出

T行,每行一个整数,代表所需要花的最少的钱数。

样例输入

2
5 2 2
13 2 1 2
2 0
8 0
5 1 4
4 0
0 3
5 2 0
13 2 1 2
2 0
8 0
5 1 4
4 0
0 3

样例输出

17
14

提示

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