问题 1025. -- 梦想庄园

1025: 梦想庄园

时间限制:1000 ms 内存限制:128 MB
提交:413 解决:121
[ 提交][ 状态][ 讨论版]

题目描述

亮亮最近在玩一款叫做“梦想庄园”的经营游戏。在游戏中,你可以耕种,养羊甚至建造纺织厂。
如果你需要制造衣服,你首先得有布匹和毛线。布匹由棉花纺织而成;毛线由羊毛制成,而羊需要饲料才能长出羊毛,最终饲料由小麦和胡萝卜制成。
假设游戏中共有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

提示

来源

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