Решение задачи №1369 «Самый длинный путь» с ACMP





Решение задачи №1369 «Самый длинный путь» с ACMP

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

Дан ориентированный взвешенный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины).

Требуется найти две вершины, кратчайший путь между которыми имеет наибольшую длину.

Входные данные
В первой строке входного файла INPUT.TXT задано число вершин N (3 ≤ N ≤ 50). Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от от 0 до 106. Гарантируется, что на главной диагонали матрицы стоят нули.

Выходные данные
В выходной файл 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