ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2034. Caravans

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???
Posted by Otrebus 8 Jun 2015 18:03
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???
Posted by kasarino 2 Aug 2015 17:05
Otrebus, thank you for strategy !
Re: What's problem with my algo???
Posted by Md. Mithun Rahman 7 Nov 2018 11:47
what will be the ans of this case, could you tell me please???