13. Авиаперелёты

Задача

Определите минимальный объём топливного бака самолёта, который позволит долететь между любыми двумя городами (с дозаправками в пути).

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

Первая строка содержит натуральное число $n$ ($1 \leqslant n \leqslant 1000$) — количество городов. Далее следует матрица $n \times n$, где $j$-е число в $i$-й строке равно расходу топлива при перелёте из города $i$ в город $j$. Все числа неотрицательны и меньше $10^9$, диагональные элементы равны нулю.

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

Выведите одно число — минимальный возможный объём бака, который позволит выполнять перелёты между любыми городами.

Пример

avia.in                avia.out
4                      10
0 10 12 16
11 0 8 9
10 13 0 22
13 10 17 0

Ограничения

  • Время: 2 секунды
  • Память: 256 мегабайт
Редакционный разбор Рассмотрим порог $X$: самолёт может перелетать только по рёбрам с расходом топлива $\le X$. Тогда задача сводится к проверке, является ли ориентированный граф, состоящий из таких рёбер, сильно связным. Минимальный подходящий $X$ можно найти бинарным поиском. Левая граница — $0$, правая — максимум на матрице. Для заданного $X$ строим граф и запускаем две обхода: проверяем достижимость всех вершин из 1-й вершины, а затем достижимость 1-й вершины из всех остальных (например, на обратном графе). Если обе проверки успешны, граф сильно связен. Иначе порог слишком мал. Так как $n \le 1000$, одна проверка стоит $O(n^2)$ (проходим по строкам матрицы), бинарный поиск даёт дополнительный множитель $\log W$ ($W$ — максимальный вес, до $10^9$). Итоговая сложность $O(n^2 \log W)$.

Mentioned by