Задача №112058. Самый короткий путь
Дан ориентированный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его и вывести. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю).
В первой строке задано число вершин n ( 1 ≤ n ≤ 200 ). Далее идёт матрица смежности графа, то есть n строк, в каждой из которых записано n чисел. j -ое число в i -ой строке матрицы смежности задает длину ребра, ведущего из i -й вершину в j -ую. Длины могут принимать любые целые значения, не превышающие по модулю 10 6 . Гарантируется, что на главной диагонали матрицы стоят нули.
Если пути не существует выведите «No path». Иначе в первой строке выведите длину пути и количество вершин на пути. Во второй строке выведите путь в порядке обхода. Если правильных ответов несколько — выведите любой.
3 0 -7 3 -2 0 10 2 215 0
No path
3 0 -7 3 7 0 10 -2 215 0
-9 3 3 1 2