|
Название задачи: Сталкер. |
 |
Условие
|
Имя входного файла: |
stalker.in |
|
Имя выходного файла: |
stalker.out |
|
Максимальное время работы на одном тесте: |
2 секунды |
|
Максимальный объем используемой памяти: |
128 мегабайт |
В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.
Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.
Формат входных данных
В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.
В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число ri - количество дорог, обозначенных на i-ой карте. Затем идут ri строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r1 + r2 + ... + rK ≤ 300 000).
Формат выходных данных
В выходной файл необходимо вывести одно число - минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число -1.
Примеры
|
stalker.in |
stalker.out |
stalker.in |
stalker.out |
|
|
5 3 1 3 4 3 1 2 1 3 2 4 1 4 5 |
2 |
5 3 2 3 2 4 5 1 2 1 2 1 3 5 4 |
-1 |
Также доступны документы в формате DOC
Решение
Тесты и проверяющая программа
Решения, написанные членами научного комитета и жюри Всероссийской олимпиады
Разбор задачи "Сталкер"
Сведем задачу к задаче поиска кратчайшего пути в графе с длинами ребер, равными 0 или 1. Затем покажем, как решать эту задачу со сложностью O(E), где E - число ребер в графе.
Рассмотрим граф состояний сталкера. Состояние - это пара (x, y), где x - это номер здания, в котором находится сталкер, а y - номер загруженной карты. Сталкер может бесплатно перейти из одного здания в другое, если на загруженной карте есть такое ребро. В этом графе такому действию соответствует ребро (x1, y) - (x2, y). Такие ребра имеют вес 0. Также сталкер может загрузить другую карту. Этому действию соответствует ребро (x, y1) - (x, y2). Такие ребра имеют вес 1. Таким образом, общее количество ребер равно M + N * K * (K - 1) / 2, где M - общее число дорог на всех картах. Но NK2 - это слишком много. Чтобы уменьшить количество ребер, применим следующий трюк:
Большую часть ребер составляют всевозможные ребра (x, y1) - (x, y2). Добавим для каждого x вершину (x, 0), и проведем для каждого y дуги (x, y) → (x, 0) с весом 0 и (x, 0) → (x, y) с весом 1. Теперь между любыми двумя вершинами (x, y1) и (x, y2) есть путь (x, y1) → (x, 0) → (x, y2) с весом 1. В модифицированном графе количество ребер равно Е = M + 2 * N * K.
Теперь в полученном графе нужно найти кратчайший путь от вершины (1, 0) до вершины (N, 0). Покажем, как решать эту задачу за время O(E).
Идея похожа на обычный поиск в ширину. Но мы будем добавлять вершины не только в конец очереди, но и в начало (то есть, мы используем вместо очереди дек, но для удобства будем и дальше называть его очередью). У каждой вершины будет пометка, показывающая, была ли вершина обработана. Также будем хранить текущее расстояние di до каждой вершины i. Вначале положим в начало очереди первую вершину, и установим расстояние до нее d1 = 0, а расстояние до остальных di = +∞, i > 1.
На каждой итерации вынимаем вершину i из начала очереди, если она уже была обработана, то пропускаем ее, иначе проделываем с ней следующее: перебираем все ребра i → j, выходящие из этой вершины и пытаемся по ним пройти. Тогда новое расстояние до вершины j будет равно d′ = di + dist(i, j), где dist(i, j) - вес ребра i → j. Если d′ < dj, то обновляем расстояние и кладем вершину j в очередь. Причем, если ребро i → j веса 1, то добавляем вершину в конец очереди, а если веса 0, то в начало очереди. При завершении итерации помечаем вершину i как обработанную. Итерации продолжаем до тех пор, пока очередь не станет пустой.
Доказательство того, что алгоритм находит кратчайшие расстояния аналогично доказательству обхода в ширину. Так же, как в поиске в ширину доказывается, что вершины обрабатываются в порядке увеличения расстояния. Поэтому вершина может быть добавлена в очередь не более двух раз. Таким образом, общее время работы с очередью O(V) и общее время обработки вершин O(E).
Также доступны документы в формате DOC
