what is the strategy for finding ...

IBelieve · Post by **IBelieve** » Sat Jan 10, 2004 9:04 pm

what is the strategy for finding the shortest path between two vertices
when at certain times certain vertices are unavailable ? e.g problem 590..always on the run

cyfra · Post by **cyfra** » Fri Feb 27, 2004 11:43 am

Hi!

If you are writing about task 590 :
there you have to use some kind of dynamic programming ...

let us assume that we have an array [1..n][1..k]
in the cell with index [a] there is an integer which is the smallest amount of money she has to spent to get to city number a after b days ...

You begin with all array filled with infinity and [1][0] = 0 <- she starts from 1 city at day 0 ...

And you have to fill this table ... and the answer will be [n][k] ..

I hope it will help you ...