【最小樹形図---朱劉アルゴリズム】hdu 4009

#include <list>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#include <stack>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <cstdlib>
#include <limits.h>
#include <time.h>
#include <string.h>
using namespace std;

#define LL long long
#define PI acos(-1.0)
#define MAX (1LL)<<61
#define MIN INT_MIN
#define eps 1e-10
#define FRE freopen("a.txt","r",stdin)
#define MOD 1000000007
#define N  1010
struct Edge{
    int u,v;
    LL cost;
}E[N*N+5];

int pre[N],vis[N],id[N];
LL in[N];
int X,Y,Z;
struct point{
    int x,y,z;
}p[N];

LL zhuliu(int root,int NV,int NE){
   LL ret=0;
   while(1){
       int i,j,k;
       for(i=0;i<NV;i++)in[i]=MAX;
       for(i=0;i<NE;i++){
           int u=E[i].u;
           int v=E[i].v;
           if(E[i].cost<in[v] && u!=v){
               pre[v]=u;
               in[v]=E[i].cost;
           }
       }
       for(i=0;i<NV;i++){
           if(i==root)continue;
           if(in[i]==MAX) return -1;
       }
       memset(id,-1,sizeof(id));
       memset(vis,-1,sizeof(vis));
       in[root]=0;
       int cnt=0;
       for(i=0;i<NV;i++){
           ret+=in[i];
           int 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]=cnt;
               }
               id[v]=cnt++;
           }
       }
       if(!cnt)break;
       for(i=0;i<NV;i++)
       if(id[i]==-1)
       id[i]=cnt++;
       for(i=0;i<NE;i++){
           int v=E[i].v;
           E[i].u=id[E[i].u];
           E[i].v=id[E[i].v];
           if(E[i].u!=E[i].v){
               E[i].cost-=in[v];
           }
       }
       NV=cnt;
       root=id[root];
   }
   return ret;
}
LL dis(point a,point b){
    LL ans =(abs(a.x-b.x)+abs(a.y-b.y)+abs(a.z-b.z))*Y;
    if(a.z<b.z)
    ans+=Z;
    return ans;
}
int main(){
    int n,m;
    while( scanf("%d %d %d %d",&n,&X,&Y,&Z) ){
        if(!n && !X && !Y && !Z)break;
        int i,j;
        for(i=1;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
        int cnt=0;
        for(i=1;i<=n;i++){
            E[cnt].u=0;
            E[cnt].v=i;
            E[cnt].cost=p[i].z*X;
            cnt++;
            scanf("%d",&m);
            while(m--){
                int a;
                scanf("%d",&a);
                E[cnt].u=i;
                E[cnt].v=a;
                if(i==a)//!!!!!!!!!!!!
                E[cnt].cost=MAX;
                else{
                    E[cnt].cost=dis(p[i],p[a]);
                }
                cnt++;
            }
        }
        LL ans=zhuliu(0,n+1,cnt);
        if(ans==-1)puts("poor XiaoA");
        else
        printf("%I64d
",ans);
    }
    return 0;
}