Another Shortest Paths Problem solution codechef

• For Solution

  Click Here!

You are in a grid of dimensions N×MN×M.

You are allowed to perform two types of operations:

• Go down, left, up, or right each for a cost of XX. Formally, if you are at the cell (i,j)(i,j) of the grid, you can go to either of the cells (i+1,j)(i+1,j), (i,j−1)(i,j−1), (i−1,j)(i−1,j) or (i,j+1)(i,j+1) at a cost of XX.
• Go diagonally down-left, down-right, up-left, up-right, for a cost of YY. Formally, if you are at the cell (i,j)(i,j) of the grid, you can go to either of the cells (i+1,j−1)(i+1,j−1), (i+1,j+1)(i+1,j+1), (i−1,j−1)(i−1,j−1) or (i−1,j+1)(i−1,j+1) at a cost of YY.

You cannot exit the grid at any point. Find the minimum cost of going to the bottom-right corner (N,M)(N,M) from the top-left corner (1,1)(1,1).

Note:Note: Since input-output is large, prefer using fast input-output methods.

Another Shortest Paths Problem solution codechef

• First line will contain TT, number of testcases. Then the testcases follow.
• Each testcase contains of a single line of input, four space separated integers integers: N,M,X,YN,M,X,Y.

Output Format

For each testcase, output the answer in a new line.

Another Shortest Paths Problem solution codechef

• 1≤T≤5⋅1051≤T≤5⋅105
• 1≤N,M,X,Y≤1061≤N,M,X,Y≤106

Sample Input 1 

3
5 6 2 5
4 7 5 6
7 8 6 5

Another Shortest Paths Problem solution codechef

 

18
33
36

Explanation

Test Case 11: We can go 44 steps down from (1,1)(1,1) to (5,1)(5,1) and then 55 steps right to (5,6)(5,6). The total cost is 2×9=182×9=18

Test Case 22: We can go 33 steps diagonally down-right from (1,1)(1,1) to (4,4)(4,4) and then 33 steps right to (4,7)(4,7). The total cost is 3×6+3×5=18+15=333×6+3×5=18+15=33

Test Case 33: We can go 66 steps diagonally down-right from (1,1)(1,1) to (7,7)(7,7) and then 11 step right to (7,8)(7,8). The total cost is 5×6+6=36

• For Solution

  Click Here!