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

3000 мс · 256 МБ · всё или ничего

Дан ориентированный граф матрицей смежности. Найдите расстояния от вершины $x$ до всех остальных.

Первая строка содержит числа $N$ ( $1 \le N \le 1000$ ) и $x$ ( $1 \le x \le N$ ).

Далее идут $N$ строк по $N$ чисел — матрица смежности. На главной диагонали нули.

Через пробел числа $d_1, \dots, d_N$ : расстояние от $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

вывод

2 2 1 1 0 -1

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.