TrainDestination.cpp

// A Dynamic Programming based solution to find min cost
// to reach station N-1 from station 0.
#include<iostream>
#include<climits>
using namespace std;

#define INF INT_MAX
#define N 4

// This function returns the smallest possible cost to
// reach station N-1 from station 0.
int minCost(int cost[][N])
{
	// dist[i] stores minimum cost to reach station i
	// from station 0.
	int dist[N];
	for (int i=0; i<N; i++)
	dist[i] = INF;
	dist[0] = 0;

	// Go through every station and check if using it
	// as an intermediate station gives better path
	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];
}

// Driver program to test above function
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;
}