【題意】：有n個地方需要供水，每個地方都可以選擇是自己挖井，還是從別的地方引水，根據方法不同和每個地方的坐標不同，花費也不同，現在給出每個地方的坐標，花費的計算方法，以及每個地方可以給哪些地方供水（即對方可以從這里引水），求給所有地方供水的最小花費。

【題解】：比賽的時候還沒有學最小樹形圖，學了之后發現這題其實就是模板題，關鍵是要有一份好的模板。顯然對于每個地方，只有一種供水方式就足夠了，這樣也能保證花費最小，而每個地方都可以自己挖井，所以是不可能出現無解的情況的，為了方便思考，我們引入一個虛擬點，把所有自己挖井的都連到這個點，邊權為挖井的花費，而如果i能從j處引水，則從j向i連邊，邊權為引水的花費，然后對這個有向圖，以虛擬點為根，求最小樹形圖即可（最小樹形圖即為有向圖的最小生成樹）。用鄰接矩陣會TLE，用鄰接表就可以ac了。

【代碼】：
  1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "cmath"
  5 using namespace std;
  6 #define maxn 1005
  7 #define maxm 1005000
  8 int n, m;
  9 #define type int
 10 const type inf = 1 << 30;
 11 int pre[maxn],id[maxn],visit[maxn], tot;
 12 type in[maxn];
 13 int root;
 14 struct house {
 15     int x, y, z;
 16 }h[maxn];
 17 struct Edge {
 18     int u,v;
 19     type cost;
 20 }et[maxm];
 21 
 22 void init() {
 23     tot = 0;
 24 }
 25 
 26 void addedge(int u, int v, type cost) {
 27     Edge e = {u, v, cost};
 28     et[tot++] = e;
 29 }
 30 
 31 type getdist(int a, int b) {
 32     return abs(h[a].x - h[b].x) +abs(h[a].y - h[b].y) +abs(h[a].z - h[b].z);
 33 }
 34 
 35 type dirmst(int root,int nv,int ne) {//點數+1,邊數+1
 36     type ret = 0;
 37     while(1)
 38     {
 39         //find the smallest in-arc
 40         fill(&in[0], &in[maxn], inf);
 41         for(int i = 0; i < ne;i++) {
 42             int u = et[i].u, v = et[i].v;
 43             if(et[i].cost < in[v] && u != v)
 44                 pre[v] = u, in[v] = et[i].cost;
 45         }
 46         //there are some nodes other than root with no in-arc connected to it
 47         for(int i = 0;i < nv;i++)
 48             if(in[i] == inf && i != root) return -1; 
 49         //find the dir circle
 50         int cntnode = 0;
 51         memset(id, -1, sizeof(id));
 52         memset(visit, -1, sizeof(visit));
 53         in[root] = 0;
 54         for(int i = 0;i < nv;i++) {
 55             ret += in[i];
 56             int v = i;
 57             while(visit[v] != i && id[v] == -1 && v != root)
 58                 visit[v] = i, v = pre[v];
 59             if(v != root && id[v] == -1) {
 60                 for(int u = pre[v]; u != v; u = pre[u])
 61                     id[u] = cntnode;
 62                 id[v] = cntnode++;
 63             }
 64         }
 65         if(cntnode == 0) break;//no circle
 66         for(int i = 0;i < nv;i++)
 67             if(id[i] == -1) id[i] = cntnode++;
 68         //compress the nodes
 69         for(int i = 0;i < ne;i++) {
 70             int v = et[i].v;
 71             et[i].u = id[et[i].u];
 72             et[i].v = id[et[i].v];
 73             if(et[i].u != et[i].v)
 74                 et[i].cost -= in[v];
 75         }
 76         nv = cntnode;
 77         root = id[root];
 78     }
 79     return ret;
 80 }
 81 int a, b, c, k, v;
 82 int main() {
 83     while(~scanf("%d%d%d%d", &n, &a, &b, &c)) {
 84         if(!n && !a && !b && !c) break;
 85         init();
 86         root = 0;
 87         for(int i = 1; i <= n; i++) {
 88             scanf("%d%d%d", &h[i].x, &h[i].y, &h[i].z);
 89             addedge(root, i, h[i].z * a);
 90         }
 91         for(int i = 1; i <= n; i++) {
 92             scanf("%d", &k);
 93             for(int j = 0; j < k; j++) {
 94                 scanf("%d", &v);
 95                 if(v == i) continue;
 96                 type cost = getdist(v, i) * b;
 97                 if(h[i].z < h[v].z) cost += c;
 98                 addedge(i, v, cost);
 99             }
100         }
101         type ans = dirmst(root, n + 1, tot);
102         printf("%d\n", ans);
103     }
104     return 0;
105 }