|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
15.07.2014, 19:37 | #1 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Задача на графы : "Автобусы" с acmp.ru
Вечер добрый.
Прошу помощи при решении задачи с acmp.ru #134 Автобусы (Время: 1 сек. Память: 16 Мб Сложность: 50%) Между некоторыми деревнями края Власюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день. Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d). Входные данные Во входном файле INPUT.TXT записано число N - общее число деревень (1 <= N <= 100), номера деревень d и v, затем количество автобусных рейсов R (0 <= R <= 10000). Затем идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t пассажир приезжает в деревню, то уехать из нее он может в любой момент времени, начиная с t. Выходные данные В выходной файл OUTPUT.TXT вывести минимальное время, когда Мария Ивановна может оказаться в деревне v. Если она не сможет с помощью указанных автобусных рейсов добраться из d в v, вывести -1. Пример INPUT.TXT 3 1 3 4 1 0 2 5 1 1 2 3 2 3 3 5 1 1 3 10 OUTPUT.TXT 5 И как же решать это чудо? (Желательно дать идею.. накодить я сам смогу(наверное)) Мои мысли.. Задачу можно решить перебором.. Но это будет иметь огроменную сложность.. В обсуждениях говорят о Дейкстре и Форде-Белмане.. Но куда их сюда засунуть я не знаю.. Посему прошу помощи.. Заранее спасибо.. Заранее спасибо! Последний раз редактировалось Simply-Art; 18.07.2014 в 09:21. Причина: поправил input файл |
18.07.2014, 06:31 | #2 |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
А проблема то в чем?
Я бы пилил поиск в ширину. Добавить лишь небольшую особенность в том, что суммируется не только вес дуг, но и время ожидание прибавляется. Рейсов много, поиск восновном будет там крутить и время тратить. Тебе ж надо будет выбрать рейсы, которые отправляются после заданного момента. Я думаю рейсы надо засунуть в set отсортированными по времени. начальный город Г, время В. Перебираешь все рейсы, выходящие из Г во время после В. Для каждого города прибытия автобуса сохраняешь оценку минимальную В + Х + Ж. Тут Х - время хода автобуса, Ж - время ожидания (автобус не сразу готов). Города, в которые смог попасть (номера городов) сохраняешь в очереди. Сохраняешь не все города, а только те, которые улучшили оценку. Берешь первый город очереди и повторяешь для него описанный выше алгоритм. Очередь кончилась? - смотри оценку для города назначения. Оценка - это и есть искомое время. Последний раз редактировалось Stilet; 18.07.2014 в 07:53. |
18.07.2014, 12:15 | #3 | ||||
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
Цитата:
Цитата:
Цитата:
|
||||
18.07.2014, 13:46 | #4 | ||
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Цитата:
Цитата:
В set потому что [log2(10000)] = 14. Это эффективно. Последний раз редактировалось rrrFer; 18.07.2014 в 13:48. |
||
18.07.2014, 13:59 | #5 | ||
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
Цитата:
|
||
18.07.2014, 14:07 | #6 | ||
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Ну можешь для каждой вершины завести словарь исходящих маршрутов. Эффективность это поднимет, но в худшем случае все равно log2(10000).
Я бы не заморчивался. Я думаю тесты мой вариант пройдет и так (по времени в т.ч.). Цитата:
Цитата:
Последний раз редактировалось rrrFer; 18.07.2014 в 14:10. |
||
18.07.2014, 16:39 | #7 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
Ваша идея была (если я прально ее понял) слить все рейсы в множество. И для каждой мы должны были перебирать возможные.. Это O(log2(n)*n^2) (с коэффициентом < 1) Ночью напишу.. |
|
18.07.2014, 22:32 | #8 | |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Цитата:
|
|
18.07.2014, 23:15 | #9 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
А т.к. у нас set.. и переход к след элементу там за O(log2(n)).. то получаем O(n*n*log2(n)) |
|
19.07.2014, 05:51 | #10 | |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,577
|
Ну да, чето туплю я.
вставляй set в каждый узел xD. Цитата:
типа того: Код:
|
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Постоянно слетает галочка "автоматически" в "Параметры Excel", "Формулы", "Вычисления в книге" | Alexsandrr | Microsoft Office Excel | 4 | 19.10.2013 14:22 |
Олимпиадная задача "Золото племени АББА" на Pascal (№7 с acmp.ru) | Ghost3 | Помощь студентам | 19 | 17.01.2013 21:04 |
Задача "Лампочки" на Pascal (№337 с acmp.ru) | Ghost3 | Помощь студентам | 18 | 01.11.2012 14:10 |
Олимпиадная задача "Встреча" (на поиск оптимального маршрута, графы) | woofer46 | Фриланс | 2 | 15.01.2012 15:26 |
при вводе на листе "магазин"- код товара появлялось "описание" товара из "склада" с "продажной ценой" | aleksei78 | Microsoft Office Excel | 13 | 25.08.2009 12:04 |