Məsələlər
Флойд - 1
Флойд - 1
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
\InputFile
В первой строке записано количество вершин графа $n~(1 \le n \le 100)$. В следующих $n$ строках записано по $n$ чисел --- матрица смежности графа ($j$-ое число в $i$-ой строке соответствует весу ребра из вершины $i$ в вершину $j$). Все числа по модулю не превышают $100$. На главной диагонали матрицы стоят нули.
\OutputFile
Выведите $n$ строк по $n$ чисел --- матрицу кратчайших расстояний между парами вершин. $j$-ое число в $i$-ой строке должно равняться весу кратчайшего пути из вершины $i$ в вершину $j$.
\includegraphics{https://static.e-olymp.com/content/73/733bc416a8faf6a8381b45e0464c6c1a7ab53aff.gif}
Giriş verilənləri #1
4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0
Çıxış verilənləri #1
0 5 7 13 12 0 2 8 11 16 0 7 4 9 11 0