[Solved] Travel Cost Solution Codevita 9 [2024]

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 <=10^5

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

#include<bits/stdc++.h>
using 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<n;i++)
        cin>>arr[i];ll m;cin>>m;
        if(arr[n-1]==-1){
        cout<<"-1";return 0;}
        else{
            for(ll i=0;i<n;i++)dp[i]=inf;
            dp[1]=arr[1];dp[0]=0;
            for(ll i=2;i<n;i++){
                if(arr[i]==-1)continue;
                for(ll j=0;j<=m+1;j++){
                    if(i-j>=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<<"-1";
            else
            cout<<dp[n-1]+arr[0];
        }
    return 0;
}

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