|
|
вернуться в форум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? 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. Otrebus, thank you for strategy ! what will be the ans of this case, could you tell me please??? 3? i am also getting 3 for this case but wrong answer on test case #2 .. That's an intersesting strategy. Now I have to find out how do you know when some paths emerge on some vertex |
|
|
