| 1 Мартынюк Максим, 17 декабря 2024 г. 19:47:51 |
| Для тех у кого WA3. Начал использовать двухсторонний граф, ЗАРАБОТАЛО!!!
|
|
|
| 2 Караулов Иван Дмитриевич, 03 января 2024 г. 22:31:59 |
| простенький бфс даже на очередях залетает
|
|
|
| 3 Дорофеев Вадим, 26 апреля 2021 г. 14:17:13 |
| Потратил 3 дня, начал с форда-беллмана, закончил им же:)
|
|
|
| 4 Касымбеков Абдусаттар Манасбекулы, 26 июля 2020 г. 13:03:05 |
| Чуть модифицированная дейкстра, не думал что пройдет, но прошло
|
|
|
| 5 МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 21 июня 2020 г. 23:01:43 |
| ford bellman accepted python 0.89c O(N*R)
|
|
|
| 6 Олангаев Дмитрий, 28 ноября 2019 г. 20:35:18 |
| Если вы случайно вместо очереди с приоритетом будете использовать обычную очередь,то пройдете 10 тестов
|
|
|
| 7 Бабин Александр Романович, 27 марта 2019 г. 6:40:51 |
| Хочу N,M<=10^6 и сложность 52%.
|
|
|
| 8 Автахов Фарит, 03 апреля 2018 г. 15:36:31 |
| матрица смежности пар не подойдет, т.к. две деревни могут повториться
|
|
|
| 9 Хилажев Линар Рафилевич, 04 июля 2017 г. 15:18:34 |
Хорошая задача.
Решил дфсом.
|
|
|
| 10 Зубашев Степан, 28 июля 2016 г. 7:27:48 |
Сдал Дэйкстрой. Т.е. машины времени в арсенале у автобусников нет, иначе всё бы отвалилось. Писал сразу исходя из рассчёта на это, но побаивался, что всё что не декларировано явно, может попасться в тестах. Как и автобусы, которые ездят за 0 времени... Фотонная тяга, не иначе :)
Задача интересна тем, что позволяет на алгоритмы Форда и Дэйкстры взглянуть под другим углом. Число рёбер варьируется в зависимости от стоимости текущей итерации. Цена рёбер соответственно тоже вычисляется в моменты сравнения. Но при этом сами алгоритмы не меняются.
|
|
|
| 11 Скаковский Юрий Евгеньевич, 30 августа 2015 г. 17:42:51 |
| Не понадобились Дейкстра и обходы :) Ленивой динамикой сделал. Собственно, от динамики остался только массив.
|
|
|
| 12 Денис Розимовский, 29 мая 2015 г. 15:06:52 |
Алгоритм Дейкстры.
С такими ограничениями, думаю, можно и обходом в глубину обойтись, но на много лучше будет в ширину.
|
|
|
| 13 Лукьянов Иван, 06 февраля 2014 г. 0:11:28 |
| Здесь обход в ширину, как и в других задачах этого сайта :)
|
|
|
| 14 Неизвестный, 24 октября 2013 г. 17:47:11 |
| Зачем ДФС??? Один проход Дейикстрой все решает...
|
|
|
| 15 Коната Изуми, 05 апреля 2013 г. 23:35:47 |
| Мне казалось что эта задача сложнее, а она сдалась с первого раза. Решил с помощью DFS'а с кешированием, что по сути полный перебор (катаемся по всем маршрутам) но без выполнения лишней работы.
|
|
|
| 16 Сафронов Евгений Сергеевич, 02 июля 2012 г. 10:09:49 |
Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена - целые от 0 до 10000) но ведь у нас деревни от 1 до N??
Деревни - да, а время может быть и 0. В любом случае никаких противоречий: 1..N попадает в данный диапазон.
|
|
|
| 17 Антон Гуликов, 03 февраля 2012 г. 21:19:02 |
А если в город мы приехали раньше, чем из него уезжают автобусы мы можем ехать или нет?
Конечно, но придется подождать :) Словом, как в жизни.
|
|
|
| 18 алексей олегович, 22 августа 2011 г. 20:00:15 |
мне не пришло в голову как декстрой делать, по-моему, самый очевидный способ-дп
Лучше всего здесь использовать алгоритм Форд-Беллмана (ФБ). Но открой вам тайну: алгоритмы Дейкстры, Флойда и ФБ - все это на самом деле ДП.
|
|
|
| 19 ~SupernaturaL_kz~, 23 мая 2011 г. 17:51:57 |
Эта задача та же самая задача что No_206_Домой_на_электричках! Я просто поменял чтение входных данных и Accepted!
Да, у них один алгоритм решения.
|
|
|
| 20 Франчук Роман Павлович, 16 апреля 2011 г. 19:16:27 |
Обычная Дейкстра.
При таких маленьких ограничениях можно даже без пирамиды.
|
|
|
