// {{{ #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 fi first #define se second #define pb push_back #define mp make_pair #define FOR(i, a, b) for(ll i = static_cast(a); i < static_cast(b); ++i) #define FORR(i, a, b) for(ll i = static_cast(a); i >= static_cast(b); --i) #define REP(i, n) FOR(i, 0, n) #define REPR(i, n) FORR(i, n, 0) #define ALL(x) (x).begin(), (x).end() #define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl; using ll = long long; using ull = unsigned long long; using P = pair; using LP = pair; using IP = pair; using LLP = pair; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; constexpr int INF = 100000000; constexpr ll LINF = 10000000000000000ll; constexpr int MOD = static_cast(1e9 + 7); constexpr double EPS = 1e-9; // {{{ popcount static int popcount(int x) { return __builtin_popcount(static_cast(x)); } static int popcount(unsigned int x) { return __builtin_popcount(x); } static int popcount(long x) { return __builtin_popcountl(static_cast(x)); } static int popcount(unsigned long x) { return __builtin_popcountl(x); } static int popcount(long long x) { return __builtin_popcountll(static_cast(x)); } static int popcount(unsigned long long x) { return __builtin_popcountll(x); } // }}} // template specialization of std::hash for std::pair namespace std { template struct hash > { size_t operator()(const pair &key) const noexcept { size_t h1 = hash()(key.first); size_t h2 = hash()(key.second); return h1 ^ (h2 << 1); } }; } // namespace std // print vector template ostream &operator<<(ostream &os, const vector &v) { size_t sz = v.size(); os << "["; for (size_t i = 0; i < sz-1; i++) { os << v[i] << ", "; } os << v[sz-1] << "]"; return os; } // print array (except char literal) template< typename T, int N, typename std::enable_if::value, std::nullptr_t>::type = nullptr> ostream &operator<<(ostream &os, const T (&v)[N]) { os << "["; for (size_t i = 0; i < N-1; i++) { os << v[i] << ", "; } os << v[N-1] << "]"; return os; } // print array template void printArray(T *arr, size_t sz) { cerr << "["; for (size_t i = 0; i < sz-1; i++) { cerr << arr[i] << ","; } if (sz > 0) cerr << arr[sz-1]; cerr << "]" << endl; } // print pair template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << ", " << p.se << ")"; return os; } static inline ll mod(ll x, ll m) { ll y = x % m; return (y >= 0 ? y : y+m); } struct Compare { //vector &x_, &y_; //Compare(vector &x, vector &y): x_(x), y_(y) {} //bool operator()(const P &lhs, const P &rhs) { // return x_[lhs.fi]+y_[lhs.se] < x_[rhs.fi]+y_[rhs.se]; //} bool operator()(const int x, const int y) { return x < y; } }; // print floating-point number // cout << fixed << setprecision(12) << // }}} int N; P p[14]; double w[14]; double dp[1<<14][14]; void solve() { REP (i, 1<<(N+1)) REP (j, N+1) dp[i][j] = LINF; dp[0][0] = 0; double W = 0; REP (i, N) W += w[i+1]; REP (S, 1<<(N+1)) { REP (i, N+1) { if (S & (1<> p[0].fi >> p[0].se; cin >> N; REP (i, N) cin >> p[i+1].fi >> p[i+1].se >> w[i+1]; solve(); return 0; } // vim:set foldmethod=marker: