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

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

HotLog


 
[Вернуться к задаче]   1
  1  Рамазанов Айтым Нурмбетович, 29 октября 2015 г. 0:17:23
     Долго ломал я голову над тем, каким алгоритмом решил я задачу. Не Декстера, не Форд-Беллман. Идея алгоритма оказалась похоже на алгоритм Флойда-Уоршелла. Вкратце алгоритм делает следующее: при считывании очередного "короткого" ребра (b, e) заново обновляется весь массив длин, при этом не забываем проверять на достижимость вершины. Алгоритм очень неэффективный (грубо говоря m*n*n итерации), но зато несложный. До этого не знал ни один из трех алгоритмов. Зато теперь приму на вооружение эти алгоритмы
  2  Евгений Сибиль, 25 сентября 2015 г. 15:02:18
     Админы, ну зачем вы так? В третьем тесте n и m записаны на разных строчках.
Сделайте, пожалуйста, по-нормальному, фиксированный формат. Мы же алгоритмы реализуем, а не играем в игру "угадай, как записаны данные". В питоне, например, данные считываются по строкам, и потом разбираются, а если вы записываете их как левой ноге захочется - становится непонятно, где падает и почему.
  3  Филипп Кофман Олегович, 26 марта 2012 г. 10:39:02
     Тесты графов с наличием отрицательных циклов есть??
     Нет. В третьем предложении условия задачи написана правда. Условиям задач можно верить. А иначе как их решать?
  4  Франчук Роман Павлович, 17 марта 2010 г. 12:39:03
     Нет нельзя. Дейкстра не умеет работать с ребрами с отрицательным весом. Можно Флойдом, но неэффективно.
  5  Березин Дмитрий Андреевич, 07 марта 2010 г. 13:28:22
     Эту задачу можно решить Дейкстрой?
  6  Коншин Андрей Сергеевич, 16 декабря 2009 г. 20:21:17
     е мое....еще бы 200 лет думал че за фигня и почему не может пройти.....пока не почитал еще раз условие и не посмотрел пробный тест......из i в j может быть несколько ребер.....нужно выбирать минимальное))) а в первом тесте минимальное ребро из 2 в 3 вершину стоит последним..вот почему работает))
  7  Барышев Валентин Валерианович, 27 октября 2009 г. 11:46:27
     a в ответе первое число всегда 0 или оно может быть разным?
     всегда 0. ведь это наикратчайший путь из 1й вершины в 1ю вершину.
  8  Шипелов Роман Борисович, 11 марта 2009 г. 0:17:03
     у вас ошибка в примере: ребру 2-->3 приписаны два раных веса
     это как раз хорошо, лучше позволяет понять задачу.
  9  Artem, 02 июля 2008 г. 23:57:16
     Подскажите где можно взять нормальный разбор этого алгоритма. ХОРОШЕЕ ОПИСАНИЕ, А НЕ САМО РЕШЕНИЕ
     Надеюсь, что когда-нибудь на этом сайте в разделе "Курс олимпиадников", но там до графов мне еще далеко...
 1

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

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