e-olymp
Задачи

Флойд - 1

Флойд - 1

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

Входные данные

В первой строке записано количество вершин графа n (1n100). В следующих n строках записано по n чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы - всегда нули.

Выходные данные

Выведите n строк по n чисел - матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #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