Решение задачи №1373 «Два профессора» с ACMP





Решение задачи №1373 «Два профессора» с ACMP

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

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

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

Входные данные
В первой строке входного файла INPUT.TXT находятся два целых числа N и M – количество зданий и количество дорог, соединяющих здания (1 ≤ N ≤ 100, 0 ≤ M ≤ N∙(N−1)/2). Далее в M строках расположены описания дорог: 3 целых числа si, ei, li – здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1 ≤ si, ei ≤ N, 0 ≤ li ≤ 100, дороги двунаправленные).

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

#include<iostream>
#define INF 1000000000
using namespace std;
int main(){
int n,i,j,k,s,t,m;
cin>>n>>m;
if (m) { int a[n][n];
for(i=0;i<n;++i)for(j=0;j<n;++j)
if(i==j)a[i][j]=0; else a[i][j]=INF;
for(k=0;k<m;++k){
cin>>i>>j;cin>>a[i-1][j-1];
a[j-1][i-1]=a[i-1][j-1];}
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; }
else cout<<0;
return 0;}



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