Задачи
Кратчайшее расстояние
Кратчайшее расстояние
Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.
Входные данные
В первой строке содержатся два натуральных числа n и x~(1 \le n \le 1000, 1 \le x \le n) — количество вершин в графе и стартовая вершина соответственно. Далее в n строках по n чисел — матрица смежности графа: в i-ой строке на j-ом месте стоит "1", если вершины i и j соединены ребром, и "0", если ребра между ними нет. На главной диагонали матрицы стоят нули.
Выходные данные
Выведите через пробел числа d_1, d_2, ..., d_n, где d_i равно -1, если путей между x и i нет, в противном случае это минимальное рвсстояние между x и i.
Пример
Входные данные #1
6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0
Выходные данные #1
2 2 1 1 0 -1