Флойд - существование
Флойд - существование
Дан ориентированный взвешенный граф. По его матрице смежности необходимо для каждой пары вершин определить, существует кратчайший путь между ними или нет.
Кратчайший путь может не существовать по двум причинам:
Нет ни одного пути.
Есть путь сколь угодно маленького веса.
Входные данные
В первой строке задается количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел, задающих матрицу смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). В ней число 0 обозначает отсутствие ребра, а любое другое число - наличие ребра соответствующего веса. Все числа по модулю не превышают 100.
Выходные данные
Выведите n строк по n чисел: j-ое число в i-ой строке должно быть равно 0, если путь из i в j не существует, 1 - если существует кратчайший путь, и 2 - если существует путь сколь угодно маленького веса.
Пример
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 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 2 2 0 0 0 2 2