e-olymp 975

Задача: 

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

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

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

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

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

Задача на e-olimp

Тесты

input output
4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0
16
5
0 5 5 6 -1
-1 0 9 8 4
-1 -1 0 3 8
6 -1 -1 0 5
-1 2 5 6 0
14

Решение:

По алгоритму Флойда (это алгоритм который способствует нахождению кротчайших расстояний между всеми вершинами взвешенного графа, благородя ему мы берем вершину и проверяем если возможно пройти через нее и это будет короче чем идти напрямик, то сохраняем длину пути через эту вершину ) мы проверяем на прочность все связи, иными словами — мы проходим все ребра и проверяем условие. Если существует альтернативный путь от одной вершины к другой, то будет ли он будет короче если да, то мы его заменяем. Таким алгоритмом мы находим все кротчайшие пути через вершины. Но в ответе должен быть максимальный из путей через вершины, поэтому приходится снова пройтись по путям через вершины (но это уже не ребра, а оптимальные длины путей) и найти кратчайший путь максимальной длины.

Related Images:

3 thoughts on “e-olymp 975

    • Постаралась исправить все ваши замечания.

  1. — «…алгоритм, который способствует нахождению…» — только способствует? А ищет какой алгоритм? И чем же он способствует?
    — Если бы этот текст написали наши иностранные студенты, я бы передал его преподавателю русского как иностранного для разбора и анализа. Если нужно, могу организовать консультацию преподавателя РКИ.

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