Page 1 of 1
what is the strategy for finding ...
Posted: Sat Jan 10, 2004 9:04 pm
by IBelieve
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
Posted: Fri Feb 27, 2004 11:43 am
by cyfra
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 ...