e-olymp 975. Флойд

Задача

Постановка задачи на e-olymp.

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

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

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

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

Вывести искомое максимальное кратчайшее расстояние.

Тесты

n matrix Результат
1 4 0   5   9   -1
-1   0   2   8
-1   -1   0   7
4   -1  -1   0
16
2 3 0   -1   2
2    0  -1
4    1   0
4
3 5 0  -1  -1  3  4
2  0  3  -1  4
-1  4  0  -1  4
3  -1  2  0  1
1  1  -1  -1  0
8

Ссылка на успешно пройденные тесты на сайте e-olymp.

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min()  находим минимальный путь из одной вершины в другую, записывая  его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *