Introduction - If you have any usage issues, please Google them yourself
Given a square grid of N* N, the top left corner is the starting point, the coordinate is (1, 1), the X-axis is positive, the Y-axis is positive, and the length of each square is 1. A car starts from the starting point and ends at the bottom right corner, whose coordinates are (N, N).
At several grid intersections, the oil depot is set up to fuel the car during the drive. The following rules shall be observed in the driving process:
(1) the car can only travel along the edge of the grid, and can be filled with oil to drive the edge of the K grid. The car was filled with oil at departure and no oil depot at the beginning and end.
(2) when the car passes a grid, if its X coordinates or Y coordinates are reduced, then the cost of the car is payable B, otherwise it will be free of charge.
(3) when the car is running, the oil tank should be filled with oil and the cost of refueling is A.
(4) add an oil depot at the grid point when needed, and pay for additional oil depot (excluding refueling costs A).
(5) (1) ~ (4) N, K, A, B and C are positive integers.
Algorithm design:
Find a route that pays the least amount of money to arrive at the destination from the starting point.
-