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