Задача на графы : "Автобусы" с acmp.ru

[Poma][a]

Вечер добрый.
Прошу помощи при решении задачи с 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


И как же решать это чудо?
(Желательно дать идею.. накодить я сам смогу(наверное))

Мои мысли..
Задачу можно решить перебором.. Но это будет иметь огроменную сложность..
В обсуждениях говорят о Дейкстре и Форде-Белмане.. Но куда их сюда засунуть я не знаю..
Посему прошу помощи.. Заранее спасибо..

Заранее спасибо!

[rrrFer]

А проблема то в чем?
Я бы пилил поиск в ширину.

Добавить лишь небольшую особенность в том, что суммируется не только вес дуг, но и время ожидание прибавляется.

Рейсов много, поиск восновном будет там крутить и время тратить. Тебе ж надо будет выбрать рейсы, которые отправляются после заданного момента.
Я думаю рейсы надо засунуть в set отсортированными по времени.

начальный город Г, время В.
Перебираешь все рейсы, выходящие из Г во время после В.
Для каждого города прибытия автобуса сохраняешь оценку минимальную
В + Х + Ж.
Тут Х - время хода автобуса, Ж - время ожидания (автобус не сразу готов).

Города, в которые смог попасть (номера городов) сохраняешь в очереди. Сохраняешь не все города, а только те, которые улучшили оценку.

Берешь первый город очереди и повторяешь для него описанный выше алгоритм.

Очередь кончилась? - смотри оценку для города назначения. Оценка - это и есть искомое время.

[Poma][a]

Последний раз редактировалось Simply-Art; Сегодня в 09:21. Причина: поправил input файл

Спасибо

Я бы пилил поиск в ширину.

Спасибо

Я думаю рейсы надо засунуть в set отсортированными по времени.

На кой? Сделать для каждой деревни список соседей, не?

Сохраняешь не все города, а только те, которые улучшили оценку.

Сходу я контрпример сообразить не могу.. Но ИМХО он имеется..

[rrrFer]

Но ИМХО он имеется..

ИМХО нет, алгоритм прост и прозрачен.

На кой? Сделать для каждой деревни список соседей, не?

тебе надо рейсы выбирать те, которые можно использовать, а не те, которые ушли пол часа назад. Поэтому по времени.
В set потому что [log2(10000)] = 14. Это эффективно.

[Poma][a]

ИМХО нет, алгоритм прост и прозрачен.

Алгоритм - да (спасибо).. а этот момент нет (ИМХО)

тебе надо рейсы выбирать те, которые можно использовать, а не те, которые ушли пол часа назад. Поэтому по времени.

И что? Солью я всё маршруты в множество, отсортирую по времени.. А дальше? Перебирать все каждый, что найти путь из A в B? А переход к следующему там за log.. Как-то не ахти..

[rrrFer]

Ну можешь для каждой вершины завести словарь исходящих маршрутов. Эффективность это поднимет, но в худшем случае все равно log2(10000).

Я бы не заморчивался. Я думаю тесты мой вариант пройдет и так (по времени в т.ч.).

Сделать для каждой деревни список соседей, не?

Список...ну ну. Где гарантия, что у одно из дереведь не будет, скажем 500 соседей. Я думаю лучше перебирать не более 14 элементов, чем 500. А может быть и не 500... Можешь для каждой деревни бахнуть set, но мне бы лень было, зачем? - этож обычная задача. Тесты проходит - хорошо, а если не проходит то продолжаем что-нибудь мутить.

Задачу можно решить перебором..

Вот перебором решить нельзя, не пройдет по времени 99%

[Poma][a]

Где гарантия, что у одно из дереведь не будет, скажем 500 соседей.

И в чем проблема? 500 - это семечки..

Ваша идея была (если я прально ее понял) слить все рейсы в множество.
И для каждой мы должны были перебирать возможные.. Это O(log2(n)*n^2) (с коэффициентом < 1)


Ночью напишу..

[rrrFer]

Ваша идея была (если я прально ее понял) слить все рейсы в множество.
И для каждой мы должны были перебирать возможные.

непрально понял. Вроде бы n*log2(n). Откуда у тебя квадрат?

[Poma][a]

Откуда у тебя квадрат?

Еще раз.. Загоняем всё в set.. Запускаем bfs.. Его сложность O(n).. Но у нас не список соседей для каждой деревни, а один set.. И чтобы найти маршруты из деревки X в деревню Y. Мы должны пробежаться по set'y.. Вот еще O(n)
А т.к. у нас set.. и переход к след элементу там за O(log2(n)).. то получаем O(n*n*log2(n))

[rrrFer]

Ну да, чето туплю я.
вставляй set в каждый узел xD.

Мы должны пробежаться по set'y.. Вот еще O(n)
А т.к. у нас set.. и переход к след элементу там за O(log2(n)).. то получаем O(n*n*log2(n))

Но ты не знаешь то есть set. Ты можешь просто последовательно его перебирать тогда время доступа О(1). Т.е. "пробежаться по сету" можно за О(N).

типа того:

set<int> myset;
for (auto t : myset) {
  cout << t;
}