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

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

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

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

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

Выведите через пробел числа d₁, d₂, ..., d_n, где d_i равно -1, если путей между x и i нет, в противном случае это минимальное рвсстояние между x и i.

Лимит времени 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

Показать классификацию задачи