Задачи
Флойд - 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