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

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

HotLog


 
[Вернуться к задаче]   1 2
  1  Дорофеев Вадим, 26 апреля 2021 г. 14:17:13
     Потратил 3 дня, начал с форда-беллмана, закончил им же:)
  2  Касымбеков Абдусаттар Манасбекулы, 26 июля 2020 г. 13:03:05
     Чуть модифицированная дейкстра, не думал что пройдет, но прошло
  3  МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 21 июня 2020 г. 23:01:43
     ford bellman accepted python 0.89c O(N*R)
  4  Олангаев Дмитрий, 28 ноября 2019 г. 20:35:18
     Если вы случайно вместо очереди с приоритетом будете использовать обычную очередь,то пройдете 10 тестов
  5  Бабин Александр Романович, 27 марта 2019 г. 6:40:51
     Хочу N,M<=10^6 и сложность 52%.
  6  Автахов Фарит, 03 апреля 2018 г. 15:36:31
     матрица смежности пар не подойдет, т.к. две деревни могут повториться
  7  Хилажев Линар Рафилевич, 04 июля 2017 г. 15:18:34
     Хорошая задача.
Решил дфсом.
  8  Зубашев Степан, 28 июля 2016 г. 7:27:48
     Сдал Дэйкстрой. Т.е. машины времени в арсенале у автобусников нет, иначе всё бы отвалилось. Писал сразу исходя из рассчёта на это, но побаивался, что всё что не декларировано явно, может попасться в тестах. Как и автобусы, которые ездят за 0 времени... Фотонная тяга, не иначе :)

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

При таких маленьких ограничениях можно даже без пирамиды.
  19  Суворов Константин Васильевич, 22 февраля 2011 г. 13:25:20
     Обычный дейкстра)
  20  Шишов Дмитрий Андреевич, 03 декабря 2010 г. 21:18:05
     Решил тупым обходом в ширину всех маршрутов.
 1 2

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

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