Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 21770. 1 - k BFS
Темы: 0-1 BFS   

Дан ориентированный взвешенный граф. Необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм 1 - k BFS.
 
Входные данные
В первой строке даны 2 целых числа n и m, число вершин и ребер в графе соответственно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра (a, b, c >= 0).
 
Выходные данные
Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.
 

 

Примеры
Входные данные Выходные данные
1
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
1 4 3 6 4 Impossible Impossible Impossible 
 

ID 33469. *Сталкер
Темы: 0-1 BFS    Дек   

В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся 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 (\(r_1 + r_2 + … + r_K <= 300 000\)).

Выходные данные: выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.

 

 

Примеры
Входные данные Выходные данные
1 12 4
4
1 6
2 4
7 9
10 12
3
1 4
7 11
3 6
3
2 5
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12
3

ID 33468. 0-1 BFS: Начало (C++)
Темы: 0-1 BFS   

По заданному изображению неориентированного графа (имеет ребра весом 0 и 1), выведите список кратчайших расстояний от вершины 0 до всех остальных.
 
Входные данные 
Дано изображение неориентированного графа с ребрами 0 и 1.
 
Выходные данные
В ответе выведите список кратчайших путей от вершины 0.