What's problem with my algo???

Posted by

gio_gio 25 Oct 2014 17:36

I run 2 bfs. The first bfs starting from node S (that is caravan's distances) and the second starting from node R (that's distances from robbers). Then i recover route for caravan and on each step backward i choose node with maximum robber distance. Minimum of robber distance on the caravans path is the answer. What's wrong?

Re: What's problem with my algo???

Posted by

gio_gio 26 Oct 2014 16:39

I've WA on 12th test

Re: What's problem with my algo???

It's because you can't greedily choose the node with the maximum robber distance. One of the other paths might contain a node with a smaller node distance somewhere further along. One such graph is here (this one is rather long, you probably just want to try to generate a graph that violates your greedy strategy yourself):

15 20

1 2

2 4

4 6

6 8

1 3

3 5

5 7

7 6

4 5

2 3

7 8

7 9

9 10

10 11

11 12

12 6

11 14

14 13

13 15

15 3

1 8 11

One strategy that works is to BFS backwards from the finishing vertex, and along each path you maintain the minimum robber distance. When two (or more) paths merge on some vertex, you consider the minimum of this path to be the maximum of the minimums of the two paths.

Re: What's problem with my algo???

Otrebus, thank you for strategy !

Re: What's problem with my algo???

what will be the ans of this case, could you tell me please???

Re: What's problem with my algo???

3?