#include using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define PRINT(a) cout << (a) << endl #define pb push_back #define eb emplace_back #define mp make_pair #define Fi first #define Se second #define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n'; using ll = long long int; using P = pair; using vi = vector; using vvi = vector; using vvvi = vector; using pii = pair; template using PQ = priority_queue; template using minPQ = priority_queue, greater>; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> x0 >> y0; int n; cin >> n; n++; int S = 1< x(n), y(n), w(n); x[0]=x0; y[0]=y0; REP(i,n-1)cin >> x[i+1] >> y[i+1] >> w[i+1]; const double INF=1e18; vector dp(S, vector(n, INF)); dp[0][0]=0; double tot = 0; REP(i,n)tot += w[i]; vector t(S,tot); REP(s, S){ REP(j,n){ if((s >> j) & 1)t[s] -= w[j]; } } vector dist(n, vector(n)); REP(i,n)REP(j,n){ dist[i][j] = abs(x[i]-x[j]) + abs((y[i]-y[j])); } REP(s, S){ // u -> v REP(u, n){ if(dp[s][u]==INF)continue; REP(v, n){ if( ~s & (1< v // REP(u, n){ // if(dp[s][u]==INF)continue; // printf("%d %d %.10f\n", s, u, dp[s][u]); // } // } printf("%.10f\n", dp[S-1][0]); }