ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 2034. Корованы

What's problem with my algo???
Послано gio_gio 25 окт 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???
Послано gio_gio 26 окт 2014 16:39
I've WA on 12th test
Re: What's problem with my algo???
Послано Otrebus 8 июн 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???
Послано kasarino 2 авг 2015 17:05
Otrebus, thank you for strategy !
Re: What's problem with my algo???
Послано Md. Mithun Rahman 7 ноя 2018 11:47
what will be the ans of this case, could you tell me please???
Re: What's problem with my algo???
Послано Mescalito 25 ноя 2018 00:20
3?
Re: What's problem with my algo???
Послано lodda 16 сен 2020 21:51
i am also getting 3 for this case but wrong answer on test case #2 ..