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

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

HotLog


 
[Вернуться к задаче]   1 2
  1  Бабин Александр Романович, 27 марта 2019 г. 6:40:51
     Хочу N,M<=10^6 и сложность 52%.
  2  Автахов Фарит, 03 апреля 2018 г. 15:36:31
     матрица смежности пар не подойдет, т.к. две деревни могут повториться
  3  Хилажев Линар Рафилевич, 04 июля 2017 г. 15:18:34
     Хорошая задача.
Решил дфсом.
  4  Зубашев Степан, 28 июля 2016 г. 7:27:48
     Сдал Дэйкстрой. Т.е. машины времени в арсенале у автобусников нет, иначе всё бы отвалилось. Писал сразу исходя из рассчёта на это, но побаивался, что всё что не декларировано явно, может попасться в тестах. Как и автобусы, которые ездят за 0 времени... Фотонная тяга, не иначе :)

Задача интересна тем, что позволяет на алгоритмы Форда и Дэйкстры взглянуть под другим углом. Число рёбер варьируется в зависимости от стоимости текущей итерации. Цена рёбер соответственно тоже вычисляется в моменты сравнения. Но при этом сами алгоритмы не меняются.
  5  Скаковский Юрий Евгеньевич, 30 августа 2015 г. 17:42:51
     Не понадобились Дейкстра и обходы :) Ленивой динамикой сделал. Собственно, от динамики остался только массив.
  6  Денис Розимовский, 29 мая 2015 г. 15:06:52
     Алгоритм Дейкстры.
С такими ограничениями, думаю, можно и обходом в глубину обойтись, но на много лучше будет в ширину.
  7  Лукьянов Иван, 06 февраля 2014 г. 0:11:28
     Здесь обход в ширину, как и в других задачах этого сайта :)
  8  Неизвестный, 24 октября 2013 г. 17:47:11
     Зачем ДФС??? Один проход Дейикстрой все решает...
  9  Коната Изуми, 05 апреля 2013 г. 23:35:47
     Мне казалось что эта задача сложнее, а она сдалась с первого раза. Решил с помощью DFS'а с кешированием, что по сути полный перебор (катаемся по всем маршрутам) но без выполнения лишней работы.
  10  Сафронов Евгений Сергеевич, 02 июля 2012 г. 10:09:49
     Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена - целые от 0 до 10000) но ведь у нас деревни от 1 до N??
     Деревни - да, а время может быть и 0. В любом случае никаких противоречий: 1..N попадает в данный диапазон.
  11  Антон Гуликов, 03 февраля 2012 г. 21:19:02
     А если в город мы приехали раньше, чем из него уезжают автобусы мы можем ехать или нет?
     Конечно, но придется подождать :) Словом, как в жизни.
  12  алексей олегович, 22 августа 2011 г. 20:00:15
     мне не пришло в голову как декстрой делать, по-моему, самый очевидный способ-дп
     Лучше всего здесь использовать алгоритм Форд-Беллмана (ФБ). Но открой вам тайну: алгоритмы Дейкстры, Флойда и ФБ - все это на самом деле ДП.
  13  ~SupernaturaL_kz~, 23 мая 2011 г. 17:51:57
     Эта задача та же самая задача что No_206_Домой_на_электричках! Я просто поменял чтение входных данных и Accepted!
     Да, у них один алгоритм решения.
  14  Франчук Роман Павлович, 16 апреля 2011 г. 19:16:27
     Обычная Дейкстра.

При таких маленьких ограничениях можно даже без пирамиды.
  15  Суворов Константин Васильевич, 22 февраля 2011 г. 13:25:20
     Обычный дейкстра)
  16  Шишов Дмитрий Андреевич, 03 декабря 2010 г. 21:18:05
     Решил тупым обходом в ширину всех маршрутов.
  17  Ситдиков Рузаль Раилевич, 29 августа 2010 г. 20:25:06
     А что нужно делать, если время отправления превышает время прибытия?
     В принципе, здесь нет автобусов со встронной машиной времени. Но если и так, то как это мешает? Разве что вы используете Дейкстру вместо Форд-Беллмана.
  18  Ivan Dvitriev Vaslylev, 11 апреля 2010 г. 23:57:55
     Форд-Беллман такой же как и в задачи "Домой на электричке", задачи почти полностью совпадают.
  19  Грачев Владимир Алексеевич, 08 октября 2009 г. 9:01:50
     И чего такое обсуждение по этой задаче,обыкновенный алгоритм Дейкстры!
     Вообще то еще проще. Здесь форд-беллман лучше подходит, да и реализация попроще.
  20  Мехрдоди Одил (ТРГИ), 16 сентября 2009 г. 1:33:48
     Надо же как обидно столько искал ошибку в реализации но все дело оказалось в том что я не вводил R чисел а вводил N(((
 1 2

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

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