CheapestRoute
SRM 407 · 2008-06-26 · by Gluk
SRM 407 · 2008-06-26 · by Gluk · Dynamic Programming
Problem Statement
Problem Statement
There is a long corridor which consists of a single horizontal row of n cells, numbered 0 to n-1 from left to right. You are standing in the leftmost cell and you want to move to the rightmost cell. From each cell, you can walk left or right to an adjacent cell. It costs cellPrice[i] to walk into cell i. If the price of a cell is -1, you cannot walk into it.
Some cells may also contain teleports. The i-th teleport is located in cell enterCell[i], and when you use that teleport, it will take you to cell exitCell[i]. It costs teleportPrice+x to use a teleport, where x is the number of teleports you have used previously. When you enter a cell i using a teleport, you do not have to pay cellPrice[i] - you only pay the teleport price. However, if the price of a cell is -1, you cannot enter that cell using a teleport.
Determine the minimal total cost C required to reach the rightmost cell. Then, determine the minimum number of moves M required to reach the rightmost cell using that minimal cost C. Walking to an adjacent cell counts as a single move, and using a teleport counts as a single move. Return aint[] containing exactly two elements. The first element should be C and the second element should be M. If it is impossible to reach the rightmost cell, return an empty int[] instead.
Some cells may also contain teleports. The i-th teleport is located in cell enterCell[i], and when you use that teleport, it will take you to cell exitCell[i]. It costs teleportPrice+x to use a teleport, where x is the number of teleports you have used previously. When you enter a cell i using a teleport, you do not have to pay cellPrice[i] - you only pay the teleport price. However, if the price of a cell is -1, you cannot enter that cell using a teleport.
Determine the minimal total cost C required to reach the rightmost cell. Then, determine the minimum number of moves M required to reach the rightmost cell using that minimal cost C. Walking to an adjacent cell counts as a single move, and using a teleport counts as a single move. Return a
Constraints
- cellPrice will contain between 1 and 50 elements, inclusive.
- enterCell will contain between 0 and 50 elements, inclusive.
- enterCell and exitCell will contain the same number of elements.
- Each element of cellPrice will be between -1 and 1000, inclusive.
- The first element of cellPrice will be between 0 and 1000, inclusive.
- teleportPrice will be between 0 and 1000, inclusive.
- Each element of enterCell and exitCell will be between 0 and n-1, inclusive, where n is the number of elements in cellPrice.
Examples
0)
{100}
{0}
{0}
1000
Returns: {0, 0 }
Here there is only one cell.
1)
{0,-1,0,0}
{0}
{2}
1000
Returns: {1000, 2 }
First, we use the teleport from cell 0 to cell 2. Then we walk from cell 2 to cell 3. Total cost is 1000+0+0=1000.
2)
{1,2,3}
{}
{}
100
Returns: {5, 2 }
There are no teleports, so we just walk from cell 0 to cell 1 and then to cell 2.
3)
{1,0,-1}
{0}
{2}
0
Returns: { }
The last cell is blocked, so we can't enter there.
4)
{1,1,100,1}
{1}
{2}
99
Returns: {101, 3 }
Submissions are judged against all 213 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CheapestRoute with a public method vector<int> routePrice(vector<int> cellPrice, vector<int> enterCell, vector<int> exitCell, int teleportPrice) · 213 test cases · 2 s / 256 MB per case