学步园

#include<stdio.h>
#include<string.h>
#include<math.h>
#define IN 9999999
#define NN 1010
int n,num;
struct op
{
    int x,y,h;
}p[NN];
struct ed
{
    int s,d,w;
}e[NN*NN];
int dis(int i,int j)
{
    return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)+abs(p[i].h-p[j].h);
}
void eadge(int s,int d,int w)
{
    e[num].s=s;e[num].d=d;e[num++].w=w;
}
int ms[NN],flag[NN],id[NN],pre[NN];
int f(int root,int nm)
{
    int sum=0;
    while(1)
    {
        memset(ms,IN,sizeof(ms));
        memset(flag,-1,sizeof(flag));
        memset(id,-1,sizeof(id));
        for(int i=0;i<num;i++)//除了根节点root以外的节点，选择一条权值最小的入边
        {
            int s=e[i].s,d=e[i].d,w=e[i].w;
            if(w>=ms[d]||d==s)continue;
            ms[d]=w;pre[d]=s;
        }
        pre[root]=root;ms[root]=0;
        for(i=0;i<nm;i++)//若有孤立点则无解
        {
            if(ms[i]==IN)return -1;
            sum+=ms[i];
        }
        int res=0;
        for(i=0;i<nm;i++)//所有被选择的边构成了一个子图中环的个数
        {
            if(flag[i]==-1)
            {
                int u=i;
                while(flag[u]==-1)
                {
                    flag[u]=i;
                    u=pre[u];
                }
                if(flag[u]!=i||u==root)continue;
                for(int t=pre[u];t!=u;t=pre[t])
                id[t]=res;
                id[u]=res++;
            }
        }
        if(res==0)break;//若无环，则解已求出
        for(i=0;i<nm;i++)
            if(id[i]==-1)id[i]=res++;//将环以外的节点加入新图
            for(i=0;i<num;i++)//收缩有向环，并且用一个新节点来代替
            {
                e[i].w-=ms[e[i].d];
                e[i].s=id[e[i].s];
                e[i].d=id[e[i].d];
            }
            nm=res;root=id[root];
    }
    return sum;
}
int main()
{
    int i,j,k,x,y,z;
    while(scanf("%d%d%d%d",&n,&x,&y,&z),n||x||y||z)
    {
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].h);
        num=0;
        for(i=1;i<=n;i++)
            eadge(0,i,p[i].h*x);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&k);
            while(k--)
            {
            scanf("%d",&j);
            if(p[j].h>p[i].h)
                eadge(i,j,dis(i,j)*y+z);
            else eadge(i,j,dis(i,j)*y);
            }
        }
        int sum=f(0,n+1);
        if(sum==-1)
            printf("poor XiaoA\n");
            else printf("%d\n",sum);
    }
    return 0;
}