|
Самый короткий путь
(Время: 1 сек. Память: 16 Мб Сложность: 42%)
Дан ориентированный взвешенный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю).
Входные данные
В первой строке входного файла INPUT.TXT задано число вершин N (3 ≤ N ≤ 50). Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать значения, не превосходящие 106 по абсолютной величине. Гарантируется, что на главной диагонали матрицы стоят нули.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – искомый минимум. Если его не существует, выведите -1.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
0 42 18468
6335 0 26501
19170 15725 0 | 42 |
| 2 | 3
0 -7 3
-2 0 10
2 215 0 | -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
