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
INF = 2147483647 NEW_LINE N = 4 NEW_LINE def minCost ( cost ) : NEW_LINE INDENT dist = [ 0 for i in range ( N ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT dist [ i ] = INF NEW_LINE DEDENT dist [ 0 ] = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( i + 1 , N ) : NEW_LINE INDENT if ( dist [ j ] > dist [ i ] + cost [ i ] [ j ] ) : NEW_LINE INDENT dist [ j ] = dist [ i ] + cost [ i ] [ j ] NEW_LINE DEDENT DEDENT DEDENT return dist [ N - 1 ] NEW_LINE DEDENT cost = [ [ 0 , 15 , 80 , 90 ] , [ INF , 0 , 40 , 50 ] , [ INF , INF , 0 , 70 ] , [ INF , INF , INF , 0 ] ] NEW_LINE print ( " The ▁ Minimum ▁ cost ▁ to ▁ reach ▁ station ▁ " , N , " ▁ is ▁ " , minCost ( cost ) ) NEW_LINE