Задачі
Флойд - 1
Флойд - 1
Повний орієнтовний зважений граф задано матрицею суміжності. Побудуйте матрицю найкоротших шляхів між його вершинами. Гарантується, що у графі немає циклів від'ємної ваги.
Вхідні дані
У першому рядку записана кількість вершин графа n~(1 \le n \le 100). У наступних n рядках записано по n чисел — матриця суміжності графа (j-те число в i-ому рядку відповідає вазі ребра з вершини i у вершину j). Всі числа за модулем не перевищують 100. На головній діагоналі матриці знаходяться нулі.
Вихідні дані
Виведіть n рядків по n чисел — матрицю найкоротших відстаней між парами вершин. j-те число у i-ому рядку повинно бути рівним вазі найкоротшого шляху з вершини i у вершину j.
Приклад
Вхідні дані #1
4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0
Вихідні дані #1
0 5 7 13 12 0 2 8 11 16 0 7 4 9 11 0