#include #include #include #include #include #define REP(i, a, b) for (int i = int(a); i < int(b); i++) #ifdef _DEBUG_ #define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl #else #define dump(val) #endif using namespace std; typedef long long int ll; template vector make_v(size_t a, T b) { return vector(a, b); } template auto make_v(size_t a, Ts... ts) { return vector(a, make_v(ts...)); } template void chmin(T &a, T b) { a = min(a, b); } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int x, y, n; cin >> x >> y >> n; vector X(n), Y(n); vector W(n); double Wsum = 0; REP(i, 0, n) { cin >> X[i] >> Y[i] >> W[i]; Wsum += W[i]; } auto dp = make_v(1 << n, n, double(1e+15)); REP(i, 0, n) { dp[1 << i][i] = (abs(x - X[i]) + abs(y - Y[i])) * (Wsum + 100) / 120; } REP(i, 1, 1 << n) { double w = 0.0; REP(j, 0, n) { if (((i >> j) & 1) == 0) { w += W[j]; } } REP(j, 0, n) { REP(k, 0, n) { int nxt = i | (1 << k); if (i == nxt) continue; int dis = abs(X[j] - X[k]) + abs(Y[j] - Y[k]); double cost = dis * (w + 100) / 120; chmin(dp[nxt][k], dp[i][j] + cost); } } } double ans = 1e+15; REP(i, 0, n) { chmin(ans, dp[(1 << n) - 1][i] + (abs(x - X[i]) + abs(y - Y[i])) * 100.0 / 120); } cout << fixed << setprecision(15) << ans + Wsum << endl; return 0; }