Hexagons (Codeforces 1421D)
Tags: Greedy, shortest paths

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 $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ 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 \le t \le 10^{4}$$$). Description of the test cases follows.The first line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$-10^{9} \le x, y \le 10^{9}$$$) representing the coordinates of the target hexagon.The second line of each test case contains six integers $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ ($$$1 \le c_1, c_2, c_3, c_4, c_5, c_6 \le 10^{9}$$$) 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.

Note: The picture below shows the solution for the first sample. The cost $$$18$$$ is reached by taking $$$c_3$$$ 3 times and $$$c_2$$$ once, amounting to $$$5+5+5+3=18$$$.  

Sample Inputs:
2
-3 1
1 3 5 7 9 11
1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Outputs:
18
1000000000000000000

Solution (Python):
inn = lambda : int(input())
inm = lambda : map(int, input().split())
ins = lambda : str(input())
ina = lambda : list(map(int, input().split()))

def solve():
    (x, y) = inm()
    c = ina()
    ans = [0, 0, 0]
    ans[0] = (x * c[5] if x >= 0 else -x * c[2]) + (y * c[1] if y >= 0 else -y * c[4])
    ans[1] = ((x - y) * c[5] if x >= y else (y - x) * c[2]) + (y * c[0] if y >= 0 else -y * c[3])
    ans[2] = ((y - x) * c[1] if y >= x else (x - y) * c[4]) + (x * c[0] if x >= 0 else -x * c[3])
    print(min(ans))

def main():
    t = 1
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 20
for _ in range(II()):
    (x, y) = MI()
    cc = LI()

    def move(x, y, d):
        cost = 0
        if d > 0:
            cost += cc[0] * d
        elif d < 0:
            cost += -cc[3] * d
        x -= d
        y -= d
        return (x, y, cost)

    def to0(x, y):
        cost = 0
        if x > 0:
            cost += cc[5] * x
        elif x < 0:
            cost += cc[2] * -x
        if y > 0:
            cost += cc[1] * y
        elif y < 0:
            cost += cc[4] * -y
        return cost
    ans = inf
    (x1, y1, cur) = move(x, y, x)
    cur += to0(x1, y1)
    ans = min(ans, cur)
    (x1, y1, cur) = move(x, y, y)
    cur += to0(x1, y1)
    ans = min(ans, cur)
    cur = to0(x, y)
    ans = min(ans, cur)
    print(ans)

Solution (Python):
if __name__ == '__main__':
    T = int(input())
    for t in range(T):
        (x, y) = tuple(map(int, input().split()))
        (c1, c2, c3, c4, c5, c6) = tuple(map(int, input().split()))
        h_p = min(c2, c1 + c3)
        h_n = min(c5, c6 + c4)
        v_p = min(c6, c1 + c5)
        v_n = min(c3, c2 + c4)
        d_p = min(c1, c2 + c6)
        d_n = min(c4, c3 + c5)
        h = h_p if y > 0 else h_n
        v = v_p if x > 0 else v_n
        cost = abs(x * v) + abs(y * h)
        d = d_p if x > 0 else d_n
        h = h_p if x < y else h_n
        cost = min(cost, abs(x * d) + abs(abs(x - y) * h))
        d = d_p if y > 0 else d_n
        v = v_p if y < x else v_n
        cost = min(cost, abs(y * d) + abs(abs(x - y) * v))
        print(cost)