Задача №173. Флойд - существование
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует ли кратчайший путь между ними или нет.
Комментарий: Кратчайший путь может не существовать по двум причинам:
В первой строке входного файла записано единственное число: \(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