goswamirahul to find minimum cost path from station 0 to station n1 where cost of moving from ith station to jth station is given as matrix of size n x n where matrixij denotes the cost of moving from station i station j for i j note that values where matrixij and i j does not mean anything and hence represented by 1 or inf for the input below cost matrix minimum cost is obtained as from 0 1 3 cost01 cost13 65 the output will be the minimum cost to reach station 4 is 65 time complexity on2 space complexity on find minimum cost keyword arguments cost matrix containing costs disti stores minimum cost from 0 i find minimum cost keyword arguments cost matrix containing costs dist i stores minimum cost from 0 i cost from 0 0 is zero cost i j is the cost of going from i j cost i j 1 for i j
INF = float("inf")


def min_cost(cost):
    
    length = len(cost)
    
    dist = [INF] * length

    dist[0] = 0   

    for i in range(length):
        for j in range(i+1,length):
            dist[j] = min(dist[j], dist[i] + cost[i][j])

    return dist[length-1]


if __name__ == '__main__':
    costs = [ [ 0, 15, 80, 90],         
             [-1,  0, 40, 50],         
             [-1, -1,  0, 70],
             [-1, -1, -1,  0] ]        
    TOTAL_LEN = len(costs)

    mcost = min_cost(costs)
    assert mcost == 65

    print(f"The minimum cost to reach station {TOTAL_LEN} is {mcost}")