text: Find the minimum cost to reach destination using a train | A Dynamic Programming based solution to find min cost to reach station N - 1 from station 0. ; This function returns the smallest possible cost to reach station N - 1 from station 0. ; dist [ i ] stores minimum cost to reach station i from station 0. ; Go through every station and check if using it as an intermediate station gives better path ; Driver program to test above function
code: #include <iostream> NEW_LINE #include <climits> NEW_LINE using namespace std ; #define INF  INT_MAX NEW_LINE #define N  4 NEW_LINE int minCost ( int cost [ ] [ N ] ) { int dist [ N ] ; for ( int i = 0 ; i < N ; i ++ ) dist [ i ] = INF ; dist [ 0 ] = 0 ; for ( int i = 0 ; i < N ; i ++ ) for ( int j = i + 1 ; j < N ; j ++ ) if ( dist [ j ] > dist [ i ] + cost [ i ] [ j ] ) dist [ j ] = dist [ i ] + cost [ i ] [ j ] ; return dist [ N - 1 ] ; } int main ( ) { int cost [ N ] [ N ] = { { 0 , 15 , 80 , 90 } , { INF , 0 , 40 , 50 } , { INF , INF , 0 , 70 } , { INF , INF , INF , 0 } } ; cout << " The ▁ Minimum ▁ cost ▁ to ▁ reach ▁ station ▁ " << N << " ▁ is ▁ " << minCost ( cost ) ; return 0 ; }