#include #include using namespace std; const int MAX_N = 20; int x[MAX_N], y[MAX_N]; double w[MAX_N]; double dp[(1 << MAX_N)][MAX_N]; bool contains(int mask, int pos) { return (mask >> pos) & 1; } int calc_manhattan_dist(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); } int main() { int n, x0, y0; cin >> x0 >> y0; cin >> n; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i] >> w[i]; } for (int mask = 1; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { if (!contains(mask, i)) continue; // not valid int visited_cnt = 0, prev_weight = w[i]; for (int pos = 0; pos < n; pos++) { if (contains(mask, pos)) visited_cnt++; else prev_weight += w[pos]; } // 酒屋から直接来た場合 if (visited_cnt == 1) { int dist = calc_manhattan_dist(x0, y0, x[i], y[i]); dp[mask][i] = (prev_weight + 100.0) / 120.0 * dist + w[i]; if (mask == 2 && i == 1) { cout << dp[mask][i] << endl; } continue; } dp[mask][i] = (1 << 28); for (int prev = 0; prev < n; prev++) { if (!contains(mask, prev) || prev == i) continue; int dist = calc_manhattan_dist(x[i], y[i], x[prev], y[prev]); double cost = (prev_weight + 100.0) / 120.0 * dist + w[i]; dp[mask][i] = min(dp[mask][i], dp[mask & ~(1 << i)][prev] + cost); } } } double ans = (1 << 28); for (int i = 0; i < n; i++) { int dist = calc_manhattan_dist(x0, y0, x[i], y[i]); ans = min(ans, dp[(1 << n) - 1][i] + 100.0 / 120.0 * dist); } cout << fixed << setprecision(10) << ans << endl; return 0; }