#include #include #include #include #include #include #include #include #include #include using namespace std; double weight(vector &w, int s){ double ret = 0; for(int i=0; i>i) & 1){ ret += w[i]; } } return ret; } double dfs(vector> &memo, vector &x, vector &y, vector &w, int s, int pos){ if(memo[s][pos] >= 0){ return memo[s][pos]; } int n = x.size()-1; double ret = 1e9; double w_ = weight(w, s|(1<>i) & 1) continue; if(i==pos) continue; int dist = abs(x[pos] - x[i]) + abs(y[pos] - y[i]); double t = (w_ + 100.0)/120.0 * dist + w[pos]; double tmp = t + dfs(memo,x,y,w, s|(1<> x_ >> y_; int n; cin >> n; vector x(n); vector y(n); vector w(n); for(int i=0; i> x[i] >> y[i] >> w[i]; } x.push_back(x_); y.push_back(y_); w.push_back(0); vector> dp(1<<(n+1), vector(n+1, -1.0)); double sum = weight(w, (1<