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

Ссылка на оригинальную статью.

Условие:

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

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

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

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

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

Решение:

Считываем число вершин, затем матрицу смежности. Записываем матрицу смежности в массив. Затем для создания матрицы минимальных путей заменяем каждый элемент матрицы на минимум из непосредственного расстояния между вершинами в матрице смежности и расстоянием между ними, проходящим через одну из их общих  вершин. Выводим матрицу минимальных путей.

Тесты:

Input Output
4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0
0 5 7 13

12 0 2 8

11 16 0 7

4 9 11 0

Код программы:

 

Сергей Завада

Сергей Завада

Студент кафедры математического обеспечения компьютерных систем Одесского национального университета имени И. И. Мечникова
Сергей Завада

Latest posts by Сергей Завада (see all)

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