#include #include #include #include #include #include #include using namespace std; const double INF = 1e8; vector x, y; vector w; string binstr(int n) { stringstream ss; ss << static_cast >(n); return ss.str(); } double calc_cost120(int from, int to, double weight_now) { return w[to] * 120 + (weight_now + 100) * (abs(x[to] - x[from]) + abs(y[to] - y[from])); } int main() { int n; x.assign(20, 0), y.assign(20, 0), w.assign(20, 0); cin >> x[0] >> y[0] >> n; double total_w = 0; for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i] >> w[i]; total_w += w[i]; } x[n+1] = x[0]; y[n+1] = y[0]; int n_stat = (1 << (n + 1)); vector weight(n_stat + 1, -1); weight[1] = total_w; vector< vector > dp(n_stat, vector(n + 1, INF)); int next_stat; dp[1][0] = 0; for (int stat = 1; stat < n_stat; stat++) { for (int from = 0; from <= n; from++) { if (dp[stat][from] == INF) { continue; } for (int to = 1; to <= n; to++) { next_stat = stat | (1 << to); if (stat == next_stat) { continue; } if (weight[next_stat] == -1) { weight[next_stat] = weight[stat] - w[to]; } /* printf("stat %s -> %s: %d -> %d: w %f -> %f: dp_from %f + calc %f = %f : dp_next %f -> ", binstr(stat).c_str(), binstr(next_stat).c_str(), from, to, weight[stat], weight[next_stat], dp[stat][from], calc_cost120(from, to, weight[stat]), dp[stat][from] + calc_cost120(from, to, weight[stat]), dp[next_stat][to]); */ dp[next_stat][to] = min(dp[next_stat][to], dp[stat][from] + calc_cost120(from, to, weight[stat])); // printf("dp_next_a %f\n", dp[next_stat][to]); } } } double ans = INF; for (int i = 1; i <= n; i++) { ans = min(ans, dp[n_stat - 1][i] + calc_cost120(i, 0, weight[next_stat])); } printf("%.12f\n", 1.0 * ans / 120); return 0; }