import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Mario_darko { class Point { public int x, y, z; public Point(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } public double dist(Point p) { double dx = x - p.x; double dy = y - p.y; double dz = z - p.z; return Math.sqrt(dx * dx + dy * dy + dz * dz); } public int hashCode() { return 31 * (31 * x + y) + z; } public boolean equals(Object o) { Point p = (Point) o; return x == p.x && y == p.y && z == p.z; } } private static final int MAX_NK = 13; private static final int MIN_XYZ = -1000; private static final int MAX_XYZ = 1000; private int n, tc, k[]; private Point mario, switches[], coins[][]; private double[] minBest; // contains solutions for each group private double[][] best; // contains shortest paths within groups private double[][] d, memo; // d - distances within a group private double[][][] dd; // distances between coins [n][k] and switches [n] private Scanner sc; private Set check; // are there duplicate points? private boolean readNext() { n = sc.nextInt(); int x = sc.nextInt(); int y = sc.nextInt(); int z = sc.nextInt(); if ((n | x | y | z) == 0) return false; tc++; check.clear(); if (n < 1 || n > MAX_NK) { System.err.printf("N out of bounds: N=%d, TC=%d\n", n, tc); } mario = new Point(x, y, z); check(mario); for (int i = 0; i < n; i++) { k[i] = sc.nextInt(); if (k[i] < 1 || k[i] > MAX_NK) { System.err.println("K out of bounds"); } x = sc.nextInt(); y = sc.nextInt(); z = sc.nextInt(); switches[i] = new Point(x, y, z); check(switches[i]); for (int j = 0; j < k[i]; j++) { x = sc.nextInt(); y = sc.nextInt(); z = sc.nextInt(); coins[i][j] = new Point(x, y, z); check(coins[i][j]); } } return true; } private void check(Point p) { if (!check.add(p)) { System.err.printf("Duplicate point in TC=%d", tc); } checkCoord(p.x); checkCoord(p.y); checkCoord(p.z); } private void checkCoord(int x) { if (x < MIN_XYZ || x > MAX_XYZ) { System.err.printf("Coordinates out of bounds in TC=%d\n", tc); } } private double solve() { for (int i = 0; i < n; i++) { calculateBest(i); // for each group, each coin, find solution when // path ends there } return combine(); // TSP on groups (each group g, has k[g] possible // connections to the next one } private double combine() { for (int i = 0; i < n; i++) { Arrays.fill(memo[i], -1); } calcDD(); double min = Double.POSITIVE_INFINITY; for (int i = 0; i < n; i++) { double t = mario.dist(switches[i]) + go2(i, 1 << i); if (t < min) min = t; } return min; } private void calcDD() { for (int i = 0; i < n; i++) { for (int j = 0; j < k[i]; j++) { for (int ii = 0; ii < n; ii++) { dd[i][j][ii] = coins[i][j].dist(switches[ii]); } } } } private double go2(int lastGroup, int usedGroups) { if (1 << n == usedGroups + 1) return minBest[lastGroup]; if (memo[lastGroup][usedGroups] >= 0) return memo[lastGroup][usedGroups]; double ret = Double.POSITIVE_INFINITY; for (int nextGroup = 0; nextGroup < n; nextGroup++) { if (((1 << nextGroup) & usedGroups) == 0) { for (int i = 0; i < k[lastGroup]; i++) { double t = best[lastGroup][i] + dd[lastGroup][i][nextGroup] + go2(nextGroup, usedGroups | (1 << nextGroup)); if (t < ret) ret = t; } } } return memo[lastGroup][usedGroups] = ret; } private void calculateBest(int group) { if (k[group] == 1) { minBest[group] = best[group][0] = switches[group] .dist(coins[group][0]); return; } calcD(group); minBest[group] = Double.POSITIVE_INFINITY; for (int lastVisited = 0; lastVisited < k[group]; lastVisited++) { for (int i = 0; i < k[group]; i++) { Arrays.fill(memo[i], -1); } double min = Double.POSITIVE_INFINITY; for (int i = 0; i < k[group]; i++) { if (i == lastVisited) continue; double t = switches[group].dist(coins[group][i]) + go(group, lastVisited, i, (1 << i) | (1 << lastVisited)); if (t < min) min = t; } best[group][lastVisited] = min; if (best[group][lastVisited] < minBest[group]) minBest[group] = best[group][lastVisited]; } } private double go(int group, int curChck, int last, int used) { if (1 << k[group] == used + 1) return d[last][curChck]; if (memo[last][used] >= 0) return memo[last][used]; double ret = Double.POSITIVE_INFINITY; for (int i = 0; i < k[group]; i++) { if (((1 << i) & used) == 0) { double t = d[last][i] + go(group, curChck, i, used | (1 << i)); if (t < ret) ret = t; } } return memo[last][used] = ret; } private void calcD(int group) { for (int i = 0; i < k[group]; i++) { for (int j = i + 1; j < k[group]; j++) { d[i][j] = d[j][i] = coins[group][i].dist(coins[group][j]); } } } private void init() { sc = new Scanner(new BufferedReader(new InputStreamReader(System.in))); k = new int[MAX_NK]; switches = new Point[MAX_NK]; coins = new Point[MAX_NK][MAX_NK]; minBest = new double[MAX_NK]; best = new double[MAX_NK][MAX_NK]; d = new double[MAX_NK][MAX_NK]; memo = new double[MAX_NK][1 << MAX_NK]; dd = new double[MAX_NK][MAX_NK][MAX_NK]; tc = 0; check = new HashSet(); } private void work() { init(); while (readNext()) { System.out.printf("%.2f\n", solve()); } System.out.close(); System.err.close(); sc.close(); } public static void main(String[] args) { new Mario_darko().work(); } }