Minimum possible travel cost among N cities | C ++ implementation of the approach ; Function to return the minimum cost to travel from the first city to the last ; To store the total cost ; Start from the first city ; If found any city with cost less than that of the previous boarded bus then change the bus ; Calculate the cost to travel from the currently boarded bus till the current city ; Update the currently boarded bus ; Finally calculate the cost for the last boarding bus till the ( N + 1 ) th city ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCost ( vector < int > & cost , int n ) { int totalCost = 0 ; int boardingBus = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( cost [ boardingBus ] > cost [ i ] ) { totalCost += ( ( i - boardingBus ) * cost [ boardingBus ] ) ; boardingBus = i ; } } totalCost += ( ( n - boardingBus ) * cost [ boardingBus ] ) ; return totalCost ; } int main ( ) { vector < int > cost { 4 , 7 , 8 , 3 , 4 } ; int n = cost . size ( ) ; cout << minCost ( cost , n ) ; return 0 ; }