Задачи
Кратчайшее расстояние
Кратчайшее расстояние
Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.
Входные данные
В первой строке содержатся два натуральных числа n и x (1 ≤ n ≤ 1000, 1 ≤ x ≤ n) - количество вершин в графе и стартовая вершина соответственно. Далее в n строках по n чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит "1", если вершины i и j соединены ребром, и "0", если ребра между ними нет. На главной диагонали матрицы стоят нули.
Выходные данные
Выведите через пробел числа d1
, d2
, ..., dn
, где di
равно -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