Решение задачи №136 «Алгоритм Флойда - 2» с ACMP





Решение задачи №136 «Алгоритм Флойда - 2» с ACMP

Условие задачи

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

Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. Элементы матрицы - целые числа от -1 до 100. На главной диагонали матрицы - всегда нули. Гарантируется, что в графе есть хотя бы одно ребро.

Выходные данные
В выходной файл OUTPUT.TXT требуется вывести искомое максимальное кратчайшее расстояние.

#include<iostream>
#define INF 1000000000
using namespace std;
int main(){
int n,i,j,k;
cin>>n;
int a[n][n];
for(i=0;i<n;++i)
for(j=0;j<n;++j){
cin>>a[i][j];
if(a[i][j]<0)a[i][j]=INF;}
for(k=0;k<n;++k)
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(a[i][j]>a[i][k]+a[k][j])
a[i][j]=a[i][k]+a[k][j];
k=0;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(a[i][j]<INF&&a[i][j]>k)
k=a[i][j];
cout<<k;
return 0;}



Условия задач взяты с сайта acmp.ru