| Автор: | Евгений Татаринов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 128 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
...
Все твои слёзы превращаю в лёд
Я спрячу сердце, его никто не найдёт
Не вижу смысла кончить этот эпизод
Я вижу выход, но не могу найти вход...
...
Василий Еремин, "Лёд", 2021 г.
У Вас есть ориентированный граф без петель на N вершинах, заданный матрицей смежности, где 1 — ребро есть, 0 — ребра нет. У Вас есть вершина, которая является выходом, и есть несколько вершин, которые являются входами (выход не может одновременно являться и входом). Определите, с какого входа надо начать, чтобы кратчайший путь от входа до выхода был минимально возможным.
В первой строке вводятся числа N, Q и finish — количество вершин, количество входов и вершина выхода. Во второй строке вводится Q чисел — вершины входов. В остальных N строках вводится матрица смежности.
Выведите вершину входа, которая подходит под условие задачи (обратите внимание, что надо вывести не индекс нужной вершины в списке входов, а саму вершину). Если таких вершин несколько, выведите вершину входа с минимальным номером. Если же ни от одного входа нельзя добраться до выхода, выведите − 1.
2 ≤ N ≤ 100
1 ≤ Q ≤ N − 1
1 ≤ finish, start ≤ N
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|