#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() typedef long long ll; using namespace std; const int inf = INT_MAX / 2; const ll infl = 1LL << 62; const double PI = 2 * acos(0.0); templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } ll gcd(ll a, ll b) { return a ? gcd(b % a, a) : b; } int N; double X[20], Y[20], W[20]; double dp[10000][20]; int main() { cin >> X[0] >> Y[0]; cin >> N; for (int i = 1; i <= N; i++) cin >> X[i] >> Y[i] >> W[i]; for (int i = 0; i < 1 << (N + 1); i++) for (int j = 0; j < N + 1; j++) dp[i][j] = infl; dp[0][0] = 0; for (int msk = 0; msk < 1 << (N + 1); msk++) { double w = 0; for (int i = 0; i < N + 1; i++) if (!(msk & 1 << i)) w += W[i]; double T = (w + 100) / 120; for (int i = 0; i < N + 1; i++) { for (int j = 0; j < N + 1; j++) { if (msk & 1 << j) continue; double dis = abs(X[j] - X[i]) + abs(Y[j] - Y[i]); chmin(dp[msk + (1 << j)][j], dp[msk][i] + dis * T + W[i]); } } } cout << dp[(1 << (N + 1)) - 1][0] << endl; }