Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Столовая

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

Сегодня у студентов праздник! В одном из новых зданий университета решили открыть столовую. Для этих целей требуется выбрать одно из зданий, в котором и будет располагаться столовая. Чтобы студенты как можно меньше отвлекались от учёбы, было решено выбрать такое здание, чтобы максимальное расстояние от него до всех остальных зданий было как можно меньше.

Помогите найти такое здание!

Входные данные

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

Примеры

INPUT.TXTOUTPUT.TXT
13 2
1 2 1
2 3 2
2
26 6
1 3 1
2 4 4
2 5 2
3 4 1
4 6 6
5 6 4
2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Алгоритм Флойда
 B. Самый длинный путь
 C. Алгоритм Флойда - 2
 D. Флойд вместо Дейкстры
 E. Самый короткий путь
 F. Есть ли цикл?
 G. Транзитивное замыкание
 H. Два профессора
 I. Столовая
 J. Слабая K-связность
 K. Опасный маршрут
 L. Существование пути
 M. Pink Floyd

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru