#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define len(val) static_cast(val.size()) #define rep(i, N) for(int i=0; i P; const int MAXN = 14; int sx, sy; int n; int xs[MAXN], ys[MAXN]; double wss[MAXN]; double wsum = 0; double dp[1 << MAXN][MAXN]; double d[MAXN][MAXN]; const int INF = 1e9; double dfs(int s, int v) { if(dp[s][v] >= 0) return dp[s][v]; if(s == (1<>u & 1)){ double wes = wsum; for(int i=0; i>i & 1) wes -= wss[i]; } res = min(res, dfs(s|1<> sx >> sy; cin >> n; rep(i, n+1){ if(i == 0){ xs[i] = sx; ys[i] = sy; wss[i] = 0; continue; } cin >> xs[i] >> ys[i] >> wss[i]; wsum += wss[i]; } n++; rep(i, n){ rep(j, n){ if(i == j){ d[i][j] = INF; }else{ d[i][j] = abs(xs[i]-xs[j])+abs(ys[i]-ys[j]); } } } memset(dp, -1, sizeof(dp)); cout << setprecision(8) << dfs(0, 0) << endl; }