e-olymp 974. Флойд-1

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

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

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

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

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

 

Сам алгоритм хорошо описан на wikipedia

А вот сам код

 

 

Радик Сиденко
Радик Сиденко

Latest posts by Радик Сиденко (see all)

One thought on “e-olymp 974. Флойд-1

  1. Работает шустро. Молодец. Но можно ещё быстрее. А так просто повторяет код решения выполненного Зелинским.
    Название я Вам сам поправил, а остальное (ключевые слова, тесты пояснения к коду и т.п.) Вы уж как-нибудь сами доделайте. Чтобы через годы не стеснятся качества оформления.

Добавить комментарий