кратчайшие пути

Профессор Флойд живёт в очень опасном районе города. Ежедневно бандиты грабят на улицах прохожих. Читая криминальную хронику, профессор Флойд вычислил вероятность быть ограбленным при проходе по каждой улице города.

 

Теперь он хочет найти наиболее безопасный путь от дома до университета, в котором он преподаёт. Иными словами, он хочет найти путь от дома до университета, для которого вероятность быть ограбленным минимальна.

 

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

В первой строке находятся два числа N и M - количество зданий и количество улиц, соединяющих здания (1<=N<=100, 1<=M<= (N*(N−1))/2. В следующей строке находятся числа S и E -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в M строках расположены описания дорог: 3 целых числа sieipi - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (1<=s_i, e_i<=N, 0<=p_i<=100 , дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.

 

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

Необходимо вывести одно число - минимальную возможную вероятность быть ограбленным. Выведите ответ с максимально возможной точностью.

Ввод	Вывод
3 3 1 3 1 2 20 1 3 50 2 3 20	0.36

 

Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в i-й строке и j-м столбце находится 1, если от вершины i можно добраться до вершины j, и 0 - иначе.

 

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

В первой строке дано число N (1<=N<=100) - число вершин в графе. Далее задана матрица смежности графа: в N строках даны по N чисел 0 или 1 в каждой. i-е число в i-й строке всегда равно 1.

 

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

Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.

Ввод	Вывод
4 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1	1 1 1 0  1 1 1 0  1 1 1 0  1 1 1 1

Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.

 

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

В первой строке вводится единственное число N (1 <= N <= 100) – количество вершин графа. В следующих N строках по N чисел задается матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы – всегда нули.

 

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

Выведите искомое максимальное кратчайшее расстояние.

Ввод	Вывод
6 0 6 8 -1 -1 -1 5 0 5 -1 -1 -1 1 7 0 -1 -1 -1 -1 -1 -1 0 6 -1 -1 -1 -1 -1 0 3 -1 -1 -1 2 -1 0	9