|
|
|
|
|
|
|
| 1 Караулов Иван Дмитриевич, 15 декабря 2023 г. 11:22:12 |
| дейкстра, просто для каждых изменения дочерних вершин чуть чуть изменится выбор новой дистанции
|
|
|
| 2 Кудрин Максим Витальевич, 15 августа 2021 г. 13:08:32 |
| Это же тот же самый алгоритм Дейкстры! Просто подогнать формат входных данных под решение 132 задачи и готово
|
|
|
| 3 Якина Ангелина Ивановна, 21 апреля 2019 г. 21:22:05 |
| Кстати, данную задачу можно решить с помощью Флойда. Ограничения позволяют :)
|
|
|
| 4 Зубашев Степан, 27 июля 2016 г. 21:24:01 |
Я тоже не понял, почему ФБ предпочтительнее Дэйкстры здесь. ФБ, судя по всему работает за N*M. По вашим же словам выходит, что M в худшем случае N*N. Разве это не приводит нас к тому, что в худшем случае ФБ имеет O(N^3)?
В то время как алгритм Дэйкстры имеет O(N^2 + M). Всё таки не кубический. Собственно, я думал, что Дэйкстра предпочительнее везде, где нет отрицательной стоимости рёбер. Поправьте меня, пожалуйста, если я не прав. Асимптотику взял с e-maxx.ru/algo/.
|
|
|
| 5 Бондарев Евгений, 22 мая 2015 г. 18:24:18 |
| Задача почти ничем не отличается от задачи Алгоритм Дейкстры, только считывание другое
|
|
|
| 6 Абдрахманов Алдияр Маулынгазынович, 24 февраля 2014 г. 10:38:09 |
| Решил Форд-Беллманом за О(2NM).
|
|
|
| 7 Индикеев Дмитрий Юрьевич, 17 ноября 2013 г. 9:27:46 |
| Я один делал поиском в глубину?? оО
|
|
|
| 8 Штыря Алексей, 02 февраля 2013 г. 2:44:01 |
| не забудьте, что до n вершины может и не быть пути
|
|
|
| 9 Mike Shvets, 18 декабря 2009 г. 1:09:16 |
Друзья, не верьте! Шарового бензина не бывает!
(>>все числа целые из диапазона от 0 до 100)
Сам проверял: ставил >0!
|
|
|
| 10 asdf, 06 сентября 2008 г. 10:39:53 |
Хотелось бы узнать ограничения на М. В условии ничего про это не сказано.
Понятно, что дорог не больше чем N*(N-1)/2, так что неявно оно существует.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
