Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Самый короткий путь

(Время: 1 сек. Память: 16 Мб Сложность: 42%)

Дан ориентированный взвешенный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю).

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

В первой строке входного файла INPUT.TXT задано число вершин N (3 ≤ N ≤ 50). Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать значения, не превосходящие 106 по абсолютной величине. Гарантируется, что на главной диагонали матрицы стоят нули.

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

В выходной файл OUTPUT.TXT выведите одно число – искомый минимум. Если его не существует, выведите -1.

Примеры

INPUT.TXTOUTPUT.TXT
13
0 42 18468
6335 0 26501
19170 15725 0
42
23
0 -7 3
-2 0 10
2 215 0
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Алгоритм Флойда
 B. Самый длинный путь
 C. Алгоритм Флойда - 2
 D. Флойд вместо Дейкстры
 E. Самый короткий путь
 F. Есть ли цикл?
 G. Транзитивное замыкание
 H. Два профессора
 I. Столовая
 J. Слабая K-связность
 K. Опасный маршрут
 L. Существование пути
 M. Pink Floyd

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru