Доброго времени суток!
Есть задача распределена она в тему DFS+BFS. Дейкстра(за M*logN)упала на последнем тесте. Да и в Дейкстре я нигде не учитывал свойства графа. Была идея разбить все ребра на ребра, равные 1/12, и запустить стандартный BFS, но мне почему-то кажется, что здесь есть другое решение :)
Не подскажите как решать ее с помощью DFS+BFS и используя свойства графа?
Заранее спасибо :)
Кратчайший путь в 1-k графе?
ну да, я же условие кинул
Можно домножить веса всех ребер на 12 и избавиться от вещественных операций, но это тоже вряд ли зайдет.
Можно попробовать Форда-Беллмана с очередью, он обычно быстро работает
я домножал на 12.
нет, задача именно на дфс или бфс (в контесте по этой теме была)
Дейкстра на
priority_queueили наset?И вроде ничего плохого нет в делении ребра на 12 частей. Должно зайти.