Блог пользователя nicky_ua

Задача на DFS+BFS
Автор nicky_ua, история, 9 лет назад, По-русски

Доброго времени суток!

Есть задача распределена она в тему DFS+BFS. Дейкстра(за M*logN)упала на последнем тесте. Да и в Дейкстре я нигде не учитывал свойства графа. Была идея разбить все ребра на ребра, равные 1/12, и запустить стандартный BFS, но мне почему-то кажется, что здесь есть другое решение :)

Не подскажите как решать ее с помощью DFS+BFS и используя свойства графа?

Заранее спасибо :)

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Кратчайший путь в 1-k графе?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно домножить веса всех ребер на 12 и избавиться от вещественных операций, но это тоже вряд ли зайдет.

Можно попробовать Форда-Беллмана с очередью, он обычно быстро работает

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    я домножал на 12.

    нет, задача именно на дфс или бфс (в контесте по этой теме была)

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Дейкстра на priority_queue или на set?

И вроде ничего плохого нет в делении ребра на 12 частей. Должно зайти.

→ Ответить