题目链接：http://codeforces.com/contest/1421/problem/D D. Hexagons time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Lindsey Buckingham told Stevie Nicks “Go your own way”. Nicks is now sad and wants to go away as quickly as possible, but she lives in a 2D hexagonal world.
Consider a hexagonal tiling of the plane as on the picture below.
Nicks wishes to go from the cell marked (0,0) to a certain cell given by the coordinates. She may go from a hexagon to any of its six neighbors you want, but there is a cost associated with each of them. The costs depend only on the direction in which you travel. Going from (0,0) to (1,1) will take the exact same cost as going from (−2,−1) to (−1,0). The costs are given in the input in the order c1, c2, c3, c4, c5, c6 as in the picture below.
Print the smallest cost of a path from the origin which has coordinates (0,0) to the given cell.
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). Description of the test cases follows.
The first line of each test case contains two integers x and y (−109≤x,y≤109) representing the coordinates of the target hexagon.
The second line of each test case contains six integers c1, c2, c3, c4, c5, c6 (1≤c1,c2,c3,c4,c5,c6≤109) representing the six costs of the making one step in a particular direction (refer to the picture above to see which edge is for each value).
Output For each testcase output the smallest cost of a path from the origin to the given cell.
Example inputCopy 2 -3 1 1 3 5 7 9 11 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 outputCopy 18 1000000000000000000 题意：从原点出发到目标点的最小花费，总共有6个方向可以走，每个方向都有确定的花费。 思路：woc，一开始我想的应该是对的，就是某一个方向与他相邻的两个方向可以更新它，然后更新完所有方向的最小值之后，然后判断四个象限，如果是一三象限的话尽量走斜线，然后用直线来补 这两种走的方式下面这种更优，证明：减去相同的部分，由于上面的斜线和直线是可以合成第二种的，所以花费大于等于2. AC代码：
#include<iostream> #include<cstring> #include<map> using namespace std; typedef long long ll; int dx[6]={1,0,-1,-1,0,1}; int dy[6]={1,1,0,-1,-1,0}; ll c[6]; map<pair<int,int>,int>mp; int main() { int t; cin>>t; mp[{1,1}]=0; mp[{0,1}]=1; mp[{-1,0}]=2; mp[{-1,-1}]=3; mp[{0,-1}]=4; mp[{1,0}]=5; /* 1 -10 -12 26 3 30 1 4 2*/ while(t--) { ll res=0; ll x,y; cin>>x>>y; for(int i=0;i<6;i++) cin>>c[i]; int cnt=0; for(int i=0;i<6;i++) for(int j=0;j<6;j++) { int x=dx[i]+dx[j]; int y=dy[i]+dy[j]; //cout<<x<<' '<<y<<' '<<c[i]<<' '<<c[j]<<endl; if(mp.count({x,y})) { // cout<<c[mp[{x,y}]]<<' '<<c[i]<<' '<<c[j]<<endl; c[mp[{x,y}]]=min(c[mp[{x,y}]],c[i]+c[j]); // cout<<x<<' '<<y<<' '<<mp[{x,y}]<<endl; } } // for(int i=0;i<6;i++) // cout<<c[i]<<' '; // cout<<endl; if(x>=0 && y>=0) { if(x>=y) { res=c[0]*y+c[5]*(x-y); // res=min(res,c[0]*y+(x-y)*c[3]); } else { res=c[0]*x+c[1]*(y-x); // res=min(res,c[0]*y+(y-x)*c[2]); } } else if(x>=0 && y<=0) { res=x*c[5]+(-y)*c[4]; } else if(x<=0 && y>=0) { res=c[2]*(-x)+y*(c[1]); } else { if((-x)>=(-y)) { res=(-y)*c[3]+((-x)-(-y))*c[2]; // res=min(res,(-x)*c[3]+((-x)+y)*c[0]); } else { res=(-x)*c[3]+((-y)-(-x))*c[4]; // res=min(res,(-y)*c[3]+((-y)+x)*c[5]); } } cout<<res<<endl; } return 0; }