問題描述
終于到周末啦！小易走在市區(qū)的街道上準備找朋友聚會，突然服務器發(fā)來警報,小易需要立即回公司修復這個緊急bug闸度。假設市區(qū)是一個無限大的區(qū)域猾骡，每條街道假設坐標是(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;
}
