Версия для печати
Убрать все задачи

---

Имя входного файла:	stalker.in
Имя выходного файла:	stalker.out
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	128 мегабайт

В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.

Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.

В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.

Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.

Формат входных данных

В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i - количество дорог, обозначенных на i-ой карте. Затем идут r_i строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r₁ + r₂ + ... + r_K ≤ 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

   Решение

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 39]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 76246

Тема:   [ Многочлены ]

Сложность: 2

В массивах a: array[0..k] of integer и b: array[0..l] of integer хранятся коэффициенты двух многочленов степеней k и l. Поместить в массив c: array[0..m] of integer коэффициенты их произведения. (Числа k,l,m — натуральные, m = k + l; элемент массива с индексом i содержит коэффициент при степени i.)

Прислать комментарий

Решение

---

Задача 98755  [Бит - реверс]

Тема:   [ Двоичная система счисления ]

Сложность: 2

Целое положительное число m записывается в двоичной системе счисления и разряды (в этой записи) переставляются в обратном порядке. Получившееся число принимается за значение функции B (m). Напечатать значения для m = 512, 513, 514, ... , 1023. Вот, для ясности, начало этой распечатки: 1, 513, 257, ...

Прислать комментарий

Решение

---

Задача 98778  [Совершенные числа]

Тема:   [ Простые числа. Разложение на простые множители ]

Сложность: 2

Натуральное число называется совершенным, если оно равно сумме все своих собственных делителей, включая 1. Напечатать все совершенные числа, меньшие, чем заданное число М.

Прислать комментарий

Решение

---

Задача 98779  [Период дроби]

Тема:   [ Дроби ]

Сложность: 2

Ввести натуральные числа m и n и напечатать период десятичной дроби m / n. Например, для дроби 1 / 7 периодом будет (142857), а если дробь конечная, то ее период состоит из одной цифры 0.

Прислать комментарий

Решение

---

Задача 98776  [Инверсия]

Тема:   [ Перестановки ]

Сложность: 2+

Пусть P = (p₁, ... , P_n ) является перестановкой чисел 1, 2, ..., n. Таблицей инверсии перестановки P называют последовательность T = (t₁, ..., t_n), в которой t_i равно числу элементов перестановки Р, стоящих (в Р) левее числа i и больших i. Например, для перестановки Р = ( 5, 9,1, 8, 2, 6, 4, 7, 3 ) чисел 1, ... , 2, ... , 9 таблица инверсий Т = ( 2, 3, 6, 4, 0, 2, 2, 1, 0 ). Написать программу, которая по заданной таблице инверсии восстанавливает перестановку.

Прислать комментарий

Решение

---

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 39]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями