Dynamic programming - optiaml rute time

samonek4

Hello,

I have following problem to solve:
Please take a look at the photo:
[link=http://www.voila.pl/401/ctbd9/?1][/link]

Input:
4 - number of stations
3 - number of changes between stations
15 3 2 10 7 - time of traveling betwen bus station
2 25 30 1 10 - time of traveling betwen railway station
7 10 5 1 - time to travel from bust station to railwey station
10 8 5 5 - time to travel form railwey station to bus station

Output:
33


I need to solve the problem using dynamic programming.
I write some code in ansi C that works properly but for input files with number of stations larger than 100 the algorithm becoming very very slov. How to solve the task properly? Any Tips?


Paul