what is the strategy for finding ...

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
IBelieve
New poster
Posts: 14
Joined: Sun Nov 16, 2003 7:40 pm

what is the strategy for finding ...

Post 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
When people agree with me I always feel that I must be wrong.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post 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 ...

Post Reply

Return to “Algorithms”