Задача №111269. Экономия на рейсах
Как вы помните, Джонни работает в министерстве финансов одной небольшой страны. По роду службы ему приходится инспектировать отечественные авиакомпании и изучать маршруты, которые те предлагают.
В стране есть N городов. По государственным законам авиакомпания должна предоставлять услуги двустороннего перелёта между некоторыми парами городов, причём в целях стандартизации продолжительность любого полёта должна составлять некоторое целое число часов. Также для фиксированной пары городов длительность рейса не должна зависеть от направления перелета.
Авиакомпания называется крупной, если с помощью рейсов этой компании можно добраться из любого города страны до любого другого. Крупная авиакомпания называется экономной, если при этом количество маршрутов, ею предлагаемое, минимально возможное, которое может быть у крупной компании.
Государственная антимонопольная служба возбудила расследование против крупной авиакомпании «Aero-float». Ей предъявлено обвинение в излишней неэкономности. Джонни было поручено проинспектировать «Aero-float» в целях обнаружения финансовых махинаций, но авиакомпания отказалась раскрывать полный список выполняемых ею прямых рейсов. После продолжительных переговоров руководство компании согласилось сообщить Джонни информацию о минимально возможной продолжительности перелёта между каждой парой городов, если использовать только прямые рейсы «Aero-float» и не учитывать время, затрачиваемое на пересадки.
Используя эту информацию, помогите Джонни установить: может ли компания «Aero-float» быть экономной или нет? Более формально, установите, существует ли набор рейсов, при котором длины кратчайших маршрутов именно такие, как было сообщено Джонни, и при котором компания является экономной?
Ваша программа должна будет обработать несколько наборов входных данных. В первой строке входного файла идёт их количество C (1 ≤ C ≤ 1 500). Далее идут C блоков входных данных в следующем формате.
В первой строке блока находится единственное целое число N (2 ≤ N ≤ 1500) — количество городов в стране.
Далее идут N строк по N целых чисел Ti, j (1 ≤ Ti, j ≤ 1 000 000): j-е число в i-й строке равняется минимальному времени в часах, требуемому на перемещение из i-го города в j-й без учёта времени, затрачиваемого на пересадки.
Гарантируется, что предоставленная информация корректна, то есть существует некоторый набор рейсов, который соответствует данному набору чисел Ti, j.
Сумма квадратов N по всем наборам входных данных не превосходит 2 250 000.
Для каждого набора входных данных выведите «YES», если компания «Aero-float» может являться экономной, или «NO» в противном случае.
2
5
0 5 4 8 7
5 0 1 3 2
4 1 0 4 3
8 3 4 0 5
7 2 3 5 0
3
0 2 2
2 0 2
2 2 0
YES
NO
Для первого набора ниже приведён возможный вариант предлагаемых компанией маршрутов, при котором она является экономной. На рисунке отрезками соединены те пары городов, между которыми есть прямые рейсы, над каждым отрезком указана продолжительность соответствующего рейса.
