e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Кратчайшее расстояние

Кратчайшее расстояние

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

Входные данные

В первой строке содержатся два натуральных числа n и x (1n1000, 1xn) - количество вершин в графе и стартовая вершина соответственно. Далее в n строках по n чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит "1", если вершины i и j соединены ребром, и "0", если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выходные данные

Выведите через пробел числа d1, d2, ..., dn, где di равно -1, если путей между x и i нет, в противном случае это минимальное рвсстояние между x и i.

prb4852.gif

Лимит времени 2 секунда
Лимит использования памяти 128 MiB
Входные данные #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