Решение задачи №1374 «Столовая» с 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 выведите одно число – номер искомого здания. Если есть несколько зданий удовлетворяющих поставленным критериям, выберите среди них здание с наименьшим номером.

Решение на C++


    #include<iostream>

#define INF 1000000000

using namespace std;

int main(){

	int s,n,i,j,m,k,z=0;

	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];

	for(i=0;i<n;++i){

	k=0;

	for(j=0;j<n;++j)

		if(a[i][j]>k)k=a[i][j];

	if(k<s){s=k;z=i;}}

	cout<<z+1;}

	else cout<<1;

return 0;}

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