eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Флойд - существование

Флойд - существование

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Дан ориентированный взвешенный граф. По его матрице смежности необходимо для каждой пары вершин определить, существует кратчайший путь между ними или нет.

Кратчайший путь может не существовать по двум причинам:

  • Нет ни одного пути.

  • Есть путь сколь угодно маленького веса.

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

В первой строке задается количество вершин графа n (1n100). В следующих n строках записано по n чисел, задающих матрицу смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). В ней число 0 обозначает отсутствие ребра, а любое другое число - наличие ребра соответствующего веса. Все числа по модулю не превышают 100.

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

Выведите n строк по n чисел: j-ое число в i-ой строке должно быть равно 0, если путь из i в j не существует, 1 - если существует кратчайший путь, и 2 - если существует путь сколь угодно маленького веса.

prb976.gif

Пример

Входные данные #1
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 -1
0 0 0 -1 0
Выходные данные #1
1 1 1 0 0
1 1 1 0 0
1 1 1 0 0
0 0 0 2 2
0 0 0 2 2