eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Флойд - 1

Флойд - 1

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Повний орієнтовний зважений граф задано матрицею суміжності. Побудуйте матрицю найкоротших шляхів між його вершинами. Гарантується, що у графі немає циклів від'ємної ваги.

Вхідні дані

У першому рядку записана кількість вершин графа 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