|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1968. Evacuation
|
| View Problem Statistics | Submit | Problem added 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 |
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Sorted Problems / | Graphs / |
| 64. Compute Paths | 1968. | 63. Even graph | 267. From Fly to Elefant | 890. Maze |
| Educational Courses / | Algorithms and Data Structures / | Graph Algorithms / |
| 693. Circular Route | 1968. | 267. From Fly to Elefant | 9. Net | 246. Path in Labyrinth |
| Problems from Contests and Camps / | School olympiads and couses of Vologda region / | Impulse - 2019 / | Graphs / |
| 208. 02 - Михаил Густокашин против бюрократии | 1968. | 204. 04 - Переливания | 1701. 05 - Maze | 292. 06 - One-way Racing |
| Problems from Contests and Camps / | School olympiads and couses of Vologda region / | Impulse, september 2020 / | Impulse-2020, graphs / |
| 792. 03 - Получи дерево | 1968. | 246. 05 - Path in Labyrinth | 208. 06 - Михаил Густокашин против бюрократии | 205. 07 - Игра в города |
| time generating 0.093 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |