/* -*- coding: utf-8 -*- * * 134.cc: No.134 走れ!サブロー君 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 13; const int NBITS = 1 << MAX_N; const double DINF = 1e60; /* typedef */ /* global variables */ int xs[MAX_N], ys[MAX_N]; double wis[MAX_N], wsums[NBITS], dp[NBITS][MAX_N]; /* subroutines */ inline int mdist(int x0, int y0, int x1, int y1) { return abs(x1 - x0) + abs(y1 - y0); } inline double btime(int bits) { return (wsums[bits] + 100) / 120; } /* main */ int main() { int sx, sy; cin >> sx >> sy; int n; cin >> n; int nbits = 1 << n; double wsum = 0.0; for (int i = 0; i < n; i++) { cin >> xs[i] >> ys[i] >> wis[i]; wsum += wis[i]; } for (int bits = 0; bits < nbits; bits++) { wsums[bits] = wsum; for (int i = 0, bi = 1; i < n; i++, bi <<= 1) { if (bits & bi) wsums[bits] -= wis[i]; dp[bits][i] = DINF; } } for (int i = 0, bi = 1; i < n; i++, bi <<= 1) dp[bi][i] = mdist(sx, sy, xs[i], ys[i]) * btime(0) + wis[i]; for (int bits = 0; bits < nbits; bits++) for (int i = 0; i < n; i++) if (dp[bits][i] < DINF) for (int j = 0, bj = 1; j < n; j++, bj <<= 1) if (! (bits & bj)) { int bitsj = bits | bj; double d = dp[bits][i] + mdist(xs[i], ys[i], xs[j], ys[j]) * btime(bits) + wis[j]; if (dp[bitsj][j] > d) dp[bitsj][j] = d; } double mint = DINF; for (int i = 0; i < n; i++) if (dp[nbits - 1][i] < DINF) { double t = dp[nbits - 1][i] + mdist(xs[i], ys[i], sx, sy) * 100.0 / 120; if (mint > t) mint = t; } printf("%.9lf\n", mint); return 0; }