水井工程

Grade 100 Open Time Wednesday, 17 June 2020, 10:30 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:30 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:30 PM
Input file water.in Output file water.out

【题目描述】水井工程(water)HDU 4009

全村人都搬到了一座山上,山上没有泉水,所以每个家庭只能挖一口井或者从其他家庭建一条水管引水过来,如果挖井,花费是房子的高度×每米x元。如果从其他家庭建一条水管引水进来,当供水家庭高度不低于取水家庭高度时,花费就是两家的曼哈顿距离×每米y元(例如A点坐标为(x1,y1,z1),B点坐标为(x2,y2,z2)时,其曼哈顿距离为|x2-x1|+|y2-y1|+|z2-z1|),如果供水家庭高度高于取水家庭高度,则还要加一个水泵钱z元。此外,有些家庭也可能不愿意引水给另一些家庭。

现在给定每个家庭的三维坐标(a,b,c),其中c表示高度,你需要计算最小花费或者告诉村长艾里这是不可能做到的。

【输入格式】

输入有多组数据,每组数据第一行包含4个整数n(1≤n≤1 000)表示户数,x(1≤x≤1 000),y(1≤y≤1 000),z(1≤z≤1 000)。

随后n行包含3个整数a,b,c,表示第i个家庭的三维坐标,坐标值均不超过1 000。

接下来的n行描述家庭之间的关系,即第n+i+1行描述了第i个家庭的关系。该行以整数k开始,接下来的k个整数表示能够从第i个家庭建水管的家庭编号。

如果n=x=y=z=0,则输入结束。

【输出格式】

每行一个整数,表示最小花费,如果无法做到,输出“poor XiaoA”。

【输入样例】

2 10 20 30

1 3 2

2 4 1

1 2

2 1 2

0 0 0 0

【输出样例】

30