Transfer water HDU - 4009

//将自己凿井那部分构造成以0为起点，凿井地为终点，所花费为边权值，然后，找以0为根（因为肯定会有自凿井）最小树形图 

//如果没有一个自打井的费用比连管低的话，无根最小树形图
//

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;

#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 0x3f3f3f3f;
const LL maxn = 1005;
int pre[maxn], id[maxn], vis[maxn], in[maxn];
int pos;
int N, X, Y, Z, w[maxn][maxn];

struct Edge {
	int u, v, w;
	Edge(int uu, int vv, int ww) {
		u = uu, v = vv, w = ww;
	}
	Edge() {}
} es[maxn*maxn];
struct Point {
	int x, y, z;
} p[maxn];

int getE(Point a,Point b) {
	int c = abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z);

	c *= Y;
	if(a.z < b.z)
		c += Z;
	return c;
}
int zhuliu(int root, int n, int m) {
	int res = 0, u, v;

	while(true) {

		//      fill(in, in+n, inf);

		for(int i=0; i<=n; i++) {
			in[i] = inf;
		}
		for(int i = 0; i < m; ++i)
			if(es[i].u != es[i].v && es[i].w < in[es[i].v]) {
				pre[es[i].v] = es[i].u;//最小边的另一端点
				in[es[i].v] = es[i].w;//每一点最小边
			}
		for(int i = 0; i < n; ++i)//不连通
			if(i!=root && in[i]==inf)
				return -1;

		int tn = 0;
		ms(id, -1);
		ms(vis, -1);

		in[root] = 0;

		for(int i = 0; i < n; ++i) {
			res += in[i];

			v = i;

			while(vis[v]!=i && id[v]==-1 && v!=root) {
				vis[v] = i;
				v = pre[v];
			}//检查是否有自回环
			if(v!=root && id[v]==-1) { //当有自回环的时候，修改环为点 （缩环）
				for(int u = pre[v]; u != v; u = pre[u])
					id[u] = tn;
				id[v] = tn++;
			}
		}
		if(tn == 0) break;//说明没有一个自回环，得结果结束

		for(int i = 0; i < n; ++i)
			if(id[i]==-1)//不在自回环里的点号更新
				id[i] = tn++;

		//建立新图继续操作
		for(int i = 0; i < m; i++) { //将边修改为点的标号，即去掉自回环
			v = es[i].v;
			es[i].u = id[es[i].u];
			es[i].v = id[es[i].v];
			if(es[i].u != es[i].v)//不在自回环里面
				es[i].w -= in[v];//若指向自回环，那么它的边权就要减少in[v]等价于整个环的边权减去in[v]
		}
		//而如果没有指向有向环，说明它与这个有向环毫无关系，那么在之前的寻找自环缩点过
		//程中已经把这条边的权值加上了，所以这里避免重复计算让这条边的权值减小in[v]会变为0

		n = tn;//点数
		root = id[root];//此时根结点点号
	}
	return res;
}

int main() {
	int T, a, b, c;

	while(~scanf("%d%d%d%d", &N, &X, &Y, &Z)) {
		if(N == 0 && X == 0 && Y == 0 && Z ==0) {
			return 0;
		}

		int L = 0;

		for(int i=1; i<=N; i++)
			scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);

		for(int i=1; i<=N; i++) {
			int k, v;

			scanf("%d", &k);

			for(int j=1; j<=k; j++) {

				scanf("%d", &v);

				es[L].u=i;
				es[L].v=v;
				es[L++].w=getE(p[i], p[v]);
			}
		}
		//自己凿井
		for(int i=1; i<=N; i++) {
			es[L].u=0;
			es[L].v=i;
			es[L++].w=p[i].z*X;
		}

		int ans = zhuliu(0, N+1, L);

		if(ans == -1) printf("poor XiaoA\n");
		else printf("%d\n", ans);
	}

	return 0;
}