There are N stations on route of a train. The train goes from station 0 to N-1. The ticket cost for all pair of stations (i, j) is given where j is greater than i. Find the minimum cost to reach the destination.
http://www.geeksforgeeks.org/find-the-minimum-cost-to-reach-a-destination-where-every-station-is-connected-in-one-direction/
Consider the following example:
Input:
cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
There are 4 stations and cost[i][j] indicates cost to reach j
from i. The entries where j < i are meaningless.
Output:
The minimum cost is 65
The minimum cost can be obtained by first going to station 1
from 0. Then from station 1 to station 3.
http://www.geeksforgeeks.org/find-the-minimum-cost-to-reach-a-destination-where-every-station-is-connected-in-one-direction/
No comments:
Post a Comment