Travel Cost solution [CodeVita Season 9]
Suresh wants to travel from city A to city B. But due to coronavirus pandemic, almost all the cities have levied entry tax into the cities so that the number of people entering the city can be limited. Suresh can skip at the most m cities at a time. Suresh has to declare his itinerary at the time of leaving city A. Thus he will have to pay upfront for the entire itinerary and also has to pay a fee to get the slips issued. Upon payment, he will be given the slips for intermediate cities where he has to show the slips to pass through, en route to his destination.
Some cities have enforced lockdown, that means those cities have blocked the entry into the cities and you will have to skip the cities in any case, such cities are represented by -1. This information is known to Suresh upfront.
Help Suresh find the minimum amount to be paid to reach from City A to City B
Travel Cost solution Codevita 9
Constraints
No of cities
Input
First-line contains an integer N, denoting the number of cities
Second-line contains N space-separated integers, where the first integer denotes the cost of issuing itinerary slips and next (N-1) integers denote the entry fee of all cities. The last integer is always the destination city. If a city is under lockdown then its entry fee will be -1.
Third line contains an integer, M which represents number of cities he can skip from a present city during his travel
Output
Single integer which represents the minimum cost Suresh has to pay to travel from city A to B, but if city B is not reachable then print -1
Time Limit
1
Examples
Example 1
Input
5
1 6 -1 5 7
1
Output
19
Explanation
Since he could skip only 1 city between the cities. He will have to pay 1+6+5+7, where 1 is the fees paid to issue slips and [6,5,7] are the fees paid for the entry to the respective cities. So the total amount he has to pay while leaving A is 19.
Example 2
Input
4
3 4 1 -1
3
Output
-1
Explanation
Since the city B is under lockdown, he cannot go to city B. Hence the output is -1
Travel Cost – codevita 92022Solutions
SOLUTION OF TRAVEL COST SOLUTION [C++] – Codevita
#includeusing namespace std; typedef long long ll; ll inf=1000000000000000000,mod=1000000007,BS,k; #define en printf("n"); int main(){ ll n;cin>>n; ll arr[n],dp[n]; for(ll i=0;i >arr[i];ll m;cin>>m; if(arr[n-1]==-1){ cout=0&&arr[i-j]!=-1&&dp[i-j]!=inf) dp[i]=min(dp[i],dp[i-j]+arr[i]); } } if(dp[n-1]==inf) cout
In this article, we have talked about the Travel Cost Problem. This is the best possible optimized solution in C++.
You may also like : Grooving Monkeys Solution | TCS
