Another Shortest Paths Problem codechef solution- 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.

Another Shortest Paths Problem solution codechef

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,j1)(i,j−1)(i1,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,j1)(i+1,j−1)(i+1,j+1)(i+1,j+1)(i1,j1)(i−1,j−1) or (i1,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

  • 1T51051≤T≤5⋅105
  • 1N,M,X,Y1061≤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

Leave a Reply

Your email address will not be published. Required fields are marked *

*