Модуль: Алгоритм Флойда


Задача

9 /10


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

Теория Нажмите, чтобы прочитать/скрыть

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

Задача

Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует ли кратчайший путь между ними или нет.
 
Комментарий: Кратчайший путь может не существовать по двум причинам:
  • Нет ни одного пути
  • Есть пути сколь угодно маленького веса
     
Входные данные
В первой строке входного файла записано единственное число: N (1 <=N <=100) — количество вершин графа. В следующих N строках по N чисел — матрица смежности графа (j-е число в i-й строке соответствует весу ребра из вершины i в вершину j): число 0 обозначает отсутствие ребра, а любое другое число — наличие ребра соответствующего веса. Все числа по модулю не превышают 100.
 
Выходные данные
Выведите N строк по N чисел. j-е число в i-й строке должно соответствовать кратчайшему пути из вершины i в вершину j. Число должно быть равно 0, если пути не существует, 1, если существует кратчайший путь, и 2, если пути существуют, но бывают пути сколь угодно маленького веса.

Примеры
Входные данные Выходные данные
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 0 0 
1 1 1 0 0 
1 1 1 0 0 
0 0 0 2 2 
0 0 0 2 2 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6414
Python3
Комментарий учителя