// yukicoder 134 走れ!サブロー君 // 2019.8.7 bal4u #include //// 高速入力 #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0'); return n; } double getdbl() { // 非負実数の入力 double x, y; int n = 0, c = gc(); do n = 10*n + (c & 0xf), c = gc(); while (c >= '0'); if (c == '.') { x = 0; y = 1, c = gc(); do y *= 0.1, x += y * (c & 0xf), c = gc(); while (c >= '0'); x += n; } else x = n; return x; } //// 優先度付きキュー(ダイクストラ法用) #define QMAX 2000000 typedef struct { int n, b; double w, t; } QUE; QUE que[QMAX]; int qsize; #define PARENT(i) ((i)>>1) #define LEFT(i) ((i)<<1) #define RIGHT(i) (((i)<<1)+1) void min_heapify(int i) { int l, r, min; QUE qt; l = LEFT(i), r = RIGHT(i); if (l < qsize && que[l].t < que[i].t) min = l; else min = i; if (r < qsize && que[r].t < que[min].t) min = r; if (min != i) { qt = que[i]; que[i] = que[min]; que[min] = qt; min_heapify(min); } } void deq() { que[0] = que[--qsize]; min_heapify(0); } void enq(int n, double t, int b, double w) { int i, min; QUE qt; i = qsize++; que[i].t = t, que[i].n = n, que[i].b = b, que[i].w = w; while (i > 0 && que[min = PARENT(i)].t > que[i].t) { qt = que[i]; que[i] = que[min]; que[min] = qt; i = min; } } //// 本問題関連 #define ABS(x) ((x)>=0?(x):-(x)) #define MAX 16 int N; int X[MAX], Y[MAX]; double W[MAX]; int d[MAX][MAX]; char vis[MAX][1<<14]; double dijkstra() { int i, n, b, lim; double w, t, ans; lim = (1<<(N+1))-1, ans = 1e20; w = 0; for (i = 0; i <= N; i++) w += W[i]; enq(0, 0.0, 1, w); while (qsize) { n = que[0].n, t = que[0].t, b = que[0].b, w = que[0].w, deq(); if (W[n] > 0.0) t += W[n], w -= W[n]; //printf("n=%d, t=%lf, b=%x, w=%lf, ans=%lf\n", n, t, b, w, ans); if (b == lim) { t += d[n][0]*5.0/6; if (t < ans) ans = t; continue; } if (vis[n][b]) continue; vis[n][b] = 1; for (i = 1; i <= N; i++) { if ((b >> i) & 1) continue; if (!vis[i][b|(1< n) n++, X[n] = x, Y[n] = y, W[n] = w; } N = n; for (i = 0; i < N; i++) for (j = i+1; j <= N; j++) d[i][j] = d[j][i] = ABS(X[j]-X[i]) + ABS(Y[j]-Y[i]); printf("%.12lf\n", dijkstra()); return 0; }