Лифты
Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.
В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.
Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.
Формат входных данных
В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki — количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+…+KL≤1000. Количество этажей в небоскребе не превосходит 1000000.
Формат выходных данных
В выходной файл выведите одно число — минимальную стоимость подъема сейфа.
В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.
Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.
Формат входных данных
В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki — количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+…+KL≤1000. Количество этажей в небоскребе не превосходит 1000000.
Формат выходных данных
В выходной файл выведите одно число — минимальную стоимость подъема сейфа.
Для нахождения маршрута минимальной стоимости сначала построим по условию задачи граф. Тогда для нахождения решения можно воспользоваться одним из стандартных алгоритмов поиска кратчайшего пути во взвешенном ориентированном графе (cм., например, "Алгоритмы: построение и анализ", Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн ).
Простейший (но не оптимальный) способ представления небоскрёба в виде графа такой: пусть каждый этаж соответствует вершине, а лифты и лестницы – ребрам, веса которых – стоимости перемещения груза по данному пути (см. рис.).
Простейший (но не оптимальный) способ представления небоскрёба в виде графа такой: пусть каждый этаж соответствует вершине, а лифты и лестницы – ребрам, веса которых – стоимости перемещения груза по данному пути (см. рис.).
Получается R вершин. При заданных в задаче ограничениях (10^6 вершин, 10^6 ребер) ни один из алгоритмов не способен найти кратчайший путь в таком графе.
Попробуем уменьшить число вершин – заметим, что этажи, на которых не останавливается ни один лифт можно удалить:
Попробуем уменьшить число вершин – заметим, что этажи, на которых не останавливается ни один лифт можно удалить:
Получаем максимум 10^3 вершин и 10^6 ребер, и соответственно, можно применить алгоритм Дейкстры.
