3. Visiting Cities There are a number of cities in a row, and there are two bus lines that go between them. They both visit all cities in order, but one may take longer than the other to go between any two cities. Starting on or moving to the Blue line takes a certain amount of extra time. There is no extra time required to start on or move to the Red line. Determine the minimum cost to move from the first city to each of the cities. Example
red =[2,3,4]
blue
=[3,1,1]
blueCost
=2
There are 4 cities numbered 0 through 3 . Times from city 0 to cities 1,2 , and 3 are at indices 0,1 , and 2 respectively in the red and blue arrays. Through the explanation, an answer array, ans, will be created. - The minimum cost to go from city 0 to itself is 0 . Now ans
=[0]
- The time from city 0 to city 1 is 2 on the Red line
3+
blueCost
=5
on the Blue line. - The blueCost applies when you start on the Blue line. - The minimum time to city 1 is 2 on the Red line, so ans
=[0,2]
. - Continuing to city 2 : - stay on the Red line, arriving at
2+3=5
- switch to the Blue line and arrive at
2+1+2=5
. - The blueCost applies when you switch to the Blue line. - In this case, you arrive at time 5 regardless of the carrier on the second leg. Now ans
=[0,2,5]
. - To get to city 3 : take the Red line, arriving at
5+4=9
stay on the Blue line arriving at
5+1=6
. - To get to city 3: take the Red line, arriving at
5+4=9
stay on the Blue line arriving at
5+1=6
. - The blueCost does not apply if you stay on the Blue line or move to the Red line. - The final ans array is
[0,2,5,6]
. Function Description Complete the function minimumCost in the editor below. minimumCost has the following parameters: int red[
n]
: the times to travel on the Red line int blue[n]: the times to travel on the Blue line int blueCost: the time penalty to start on or switch to the Blue line Returns int[n]: the minimum cost of visiting each of the other cities from city 0 Constraints -
2≤n≤2×10
5
-
1≤
red[i], blue[i], blueCost
≤10
9
- Input Format For Custom Testing The first line contains an integer,
n
, the size of redD. Each of the following
n
lines contains an integer, red[i]. The next line contains an integer,
n
, the size of blue[. Each of the following
n
lines contains an integer, blue[i]. The last line contains an integer, blueCost. -
2≤n≤2×10
5
-
1≤
red[i], blue[i], blueCost
≤10
9
Input Format For Custom Testing The first line contains an integer,
n
, the size of redD. Each of the following
n
lines contains an integer, red[i]. The next line contains an integer,
n
, the size of blue[. Each of the following
n
lines contains an integer, blue[i]. The last line contains an integer, bluecost. Sample Case 0 Sample Input For Custom Testing Sample Output 0 4 Explanation You are already at city-0 so the time taken to reach city-0 is 0 . The time to reach city-1 from city-0: take the Red line: 5 . take the Blue line:
3+1=4
. The minimum time to reach city-1 is 4 .
