問題描述

終于到周末啦！小易走在市區(qū)的街道上準備找朋友聚會，突然服務(wù)器發(fā)來警報,小易需要立即回公司修復(fù)這個緊急bug。假設(shè)市區(qū)是一個無限大的區(qū)域，每條街道假設(shè)坐標是(X，Y)，小易當前在(0，0)街道，辦公室在(gx,gy)街道上。小易周圍有多個出租車打車點，小易趕去辦公室有兩種選擇，一種就是走路去公司，另外一種就是走到一個出租車打車點，然后從打車點的位置坐出租車去公司。每次移動到相鄰的街道(橫向或者縱向)走路將會花費walkTime時間，打車將花費taxiTime時間。小易需要盡快趕到公司去，現(xiàn)在小易想知道他最快需要花費多少時間去公司。

輸入描述

輸入數(shù)據(jù)包括五行:
第一行為周圍出租車打車點的個數(shù)n(1 ≤ n ≤ 50)
第二行為每個出租車打車點的橫坐標tX[i] (-10000 ≤ tX[i] ≤ 10000)
第三行為每個出租車打車點的縱坐標tY[i] (-10000 ≤ tY[i] ≤ 10000)
第四行為辦公室坐標gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔
第五行為走路時間walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔

輸出描述

輸出一個整數(shù)表示，小易最快能趕到辦公室的時間

輸入例子

2
-2 -2
0 -2
-4 -2
15 3

輸出例子

42

分析

數(shù)據(jù)空間很?。╗1,50]），窮舉即可

note

題目中的距離是曼哈頓距離

代碼

#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

int manhattan(int x1, int y1, int x2 = 0, int y2 = 0)
{
    return abs(x1 - x2) + abs(y1 - y2);
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> tx(n);
    vector<int> ty(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &tx[i]);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &ty[i]);
    }
    int gx, gy;
    scanf("%d %d", &gx, &gy);
    int wt, tt;
    scanf("%d %d", &wt, &tt);

    int st = wt * manhattan(gx, gy);
    for (int i = 0; i < n; i++)
    {
        int t = wt * manhattan(tx[i], ty[i]) + tt * manhattan(tx[i], ty[i], gx, gy);
        if (t < st)
        {
            st = t;
        }
    }

    printf("%d\n", st);

    return 0;
}