Задача:
Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
Входные данные
В первой строке содержится количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.
Выходные данные
Вывести искомое максимальное кратчайшее расстояние.
|
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 |
#include <cstdlib> #include <iostream> using namespace std; int main(){ int n; cin >> n; int a[n][n]; long long maxr = 0; for( int i=0 ; i<n ; i++ ){ for( int j=0 ; j<n ; j++ ){ cin >> a[i][j]; } } for( int k=0 ; k<n ; k++ ){ for( int i=0 ; i<n ; i++ ){ for( int j=0 ; j<n ; j++ ){ if(i != j && a[i][k] != -1 && a[k][j] != -1){ if(a[i][j] == -1){ a[i][j] = a[i][k] + a[k][j]; } else { a[i][j] = min(a[i][j], a[i][k] + a[k][j]); } } } } } for( int i=0 ; i<n ; i++ ) { for( int j=0 ; j<n ; j++ ) { if(a[i][j] > maxr) maxr = a[i][j]; } } cout << maxr << endl; } |
Задача на 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 |
Решение:
По алгоритму Флойда (это алгоритм который способствует нахождению кротчайших расстояний между всеми вершинами взвешенного графа, благородя ему мы берем вершину и проверяем если возможно пройти через нее и это будет короче чем идти напрямик, то сохраняем длину пути через эту вершину ) мы проверяем на прочность все связи, иными словами — мы проходим все ребра и проверяем условие. Если существует альтернативный путь от одной вершины к другой, то будет ли он будет короче если да, то мы его заменяем. Таким алгоритмом мы находим все кротчайшие пути через вершины. Но в ответе должен быть максимальный из путей через вершины, поэтому приходится снова пройтись по путям через вершины (но это уже не ребра, а оптимальные длины путей) и найти кратчайший путь максимальной длины.
— Что означает выражение «самый максимальный»? У меня даже предположения нет.
— Нужна ссылка на описание алгоритма Флойда, на который вы опираетесь.
— Нужно дать более детальное описание алгоритма.
Постаралась исправить все ваши замечания.
— «…алгоритм, который способствует нахождению…» — только способствует? А ищет какой алгоритм? И чем же он способствует?
— Если бы этот текст написали наши иностранные студенты, я бы передал его преподавателю русского как иностранного для разбора и анализа. Если нужно, могу организовать консультацию преподавателя РКИ.