Квадратная таблица n´n заполнена неотрицательными вещественными числами. Число a_ij, стоящее в клетке (i,j) (i- номер строки, j-номер столбца) определяет курс обмена валюты i на валюту j. Так, например, если a_ij=2.5, то это значит, что за единицу валюты i дают 2.5 единиц валюты j. Если a_ij=0, то считается, что курс обмена валюты i на валюту j прямо не установлен. Написать программу, позволяющую определить, можно ли, имея некоторую сумму денег в одной из валют, получить большую сумму денег в той же валюте, совершив несколько обменов.

Пусть задана матрица обменов Курс[i,j]i, j=1,...,n.

Будем вычислять матрицу лучших обменов (понятно, что имеет смысл вычислять только наилучшие обмены) по правилу

Новый_Обмен[i,j]=max{Обмен[i,k]*Обмен[k,j], Обмен[i,j]}

где максимум берется по всем возможным значениям k=1,...,n для всех возможных пар i,j=1,...,n. Очевидно, что на первом этапе матрица лучших курсов совпадает с матрицей обменных курсов.

Перевычисление элементов матрицы Новый_Обмен[i,j] осуществляется до тех пор, пока в матрице происходят изменения или на диагонали появился элемент, больший 1. В последнем случае индекс диагонального элемента и определяет номер валюты, для которой возможен требуемая по условию задачи цепочка обменов. Если же изменения в матрице наилучших обменов закончились, а на диагонали нет элементов, больших 1, то требуемой цепочки обменов нет.