Задача
Постановка задачи на 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.
Решение
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.*; public class Graph { public static void main(String[] args){ Scanner input = new Scanner(System.in); int n, max = 0; n = input.nextInt(); int[][] matrix = new int[n][n]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ matrix[i][j] = input.nextInt(); } } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++){ if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){ if(matrix[j][k] == -1) matrix[j][k] = matrix[j][i] + matrix[i][k]; else matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]); } } } } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(matrix[i][j] > max) max = matrix[i][j]; } } System.out.println(max); } } |
Пояснения
Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min() находим минимальный путь из одной вершины в другую, записывая его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.