Quizes
Problems
Courses
Sign
Register
Main
/
Courses
/
Theory of Graphs
/
Алгоритм Флойда
Алгоритм Флойда
№ 9
/10
Флойд - существование
Read Theory
Путь проходящий через цикл отрицательного веса становится невозможным.
Task
Time limit:
1000
ms,
Memory limit:
256 Mb
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует ли кратчайший путь между ними или нет.
Комментарий: Кратчайший путь может не существовать по двум причинам:
Нет ни одного пути
Есть пути сколь угодно маленького веса
Входные данные
В первой строке входного файла записано единственное число: 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 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
Auto
CHOOSE THE PROGRAMMING NECESSARY LANGUAGE!
Attach the program source file:
or enter the source code in the language:
C++
Python
FreePascal
PascalABC.Net
Kumir
Java
JavaScript
TypeScript
C#
F#
Swift
Rules for designing programs and a list of errors during automatic task verification
Results: