|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1968. Эвакуация
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
База одной сверхсекретной организации, чьё название мы не имеем право разглашать, представляет собой сеть из N подземных бункеров, пронумерованных от 1 до N. Некоторые пары бункеров соединены равными по длине туннелями. Также в некоторых бункерах имеются специальные засекреченные выходы, через которые осуществляется связь с внешним миром. Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего выхода. Входные данные В первой строке записано число N, во второй – число K (1 ≤ N ≤ 100000, 1 ≤ K ≤ N) – количество бункеров и количество выходов соответственно. Далее через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы. Потом идёт целое число M (1 ≤ M ≤ 100000) – количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединённых туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров. Выходные данные Выведите N чисел, разделённых пробелом – для каждого из бункеров минимальное время, необходимое, чтобы добраться до выхода. Считайте, что время перемещения по одному любому туннелю равно 1. Если из каких-то бункеров вообще нельзя добраться до выхода (а в сверхсекретных организациях бывает и не такое), то выведите для таких бункеров -1. Примеры Входные данные 3 Выходные данные 1 0 1 Входные данные 5 Выходные данные 0 0 1 -1 -1 |
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи по темам / | Графы / |
| 63. Четный граф | 1968. |
| Учебные курсы / | Алгоритмы и структуры данных / | Алгоритмы на графах / |
| 247. Удаление клеток | 1968. |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | Импульс, смена 2019 / | Графы / |
| 208. 02 - Михаил Густокашин против бюрократии | 1968. | 204. 04 - Переливания | 1701. 05 - Лабиринт | 292. 06 - Одностороннее движение |
| Задачи с соревнований и сборов / | Школьные олимпиады и курсы Вологодской области / | Импульс, сентябрь 2020 / | Импульс-2020, графы / |
| 792. 03 - Получи дерево | 1968. | 246. 05 - Путь в лабиринте | 208. 06 - Михаил Густокашин против бюрократии | 205. 07 - Игра в города |
| время генерации 0.109 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |