Home Programming CodeVita Travel Cost solution Codevita 9

[Solved] Travel Cost solution Codevita 9 [2020]

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 9 2020 Solutions

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here

15 + fourteen =

Most Popular

5 Best Wireless Neckband under Rs. 2000 – October 2020

If you are looking for Best Wireless Neckband under 2000, then you are at right place. We have covered all best neckbands...

15 Best Easiest Programming Languages in the World in 2020

A programming language in today’s generation can really ace up one’s skill set and benefit you in the long run. Having said...

Carl Pei – “Thank You OnePlus”

Just with a simple "Thank You" message , Carl Pei on Friday left OnePlus. He was the Man behind the Success of...

What is cloud computing? Introduction to Cloud Computing

In this article we will talk about one of the most trending and important technologies, which is playing a pivotal in our...

Recent Comments