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