Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


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

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru