| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 64 Мб | |
| Максимальный балл: | 100 |
Команда разработчиков игры реализовала уровень с достаточно большой картой, разделенной на N секторов. Теперь они хотят на карте разместить портал, через который персонаж игрока попадает на уровень, так, чтобы путешествие в самый удаленный сектор от этого портала заняло минимальное время.
Если в секторе i расположить портал, то путешествие в сектор j займет время a[i,j] + a[j,i] (при этом i не равно j). Помогите команде разработчиков найти такой сектор, путешествие из которого до самого удаленного от него сектора займет минимальное время.
Пусть время путешествия задано массивом целых неотрицательных чисел а, размер которого N×N. Будем считать a[i,i] = 0.
Напишите программу для решения этой задачи!
В первой строке вводится число N – количество секторов на карте, 0 < N ≤ 100.
В следующих строках вводятся элементы массива a через пробел построчно, где 0 ≤ a[i,j] ≤ 1000.
В единственной строке выведите единственное целое число – номер сектора, в котором следует расположить портал.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|