Учёный-ботаник получил карту дорог страны Лимония. Чтобы составить план исследования этой страны, ему требуется найти кратчайшие расстояния между каждой парой городов этой страны (можно ехать только по проложенным дорогам). Помогите учёному – напишите программу, которая решает эту задачу.
Входные данные
В первой строке вводится количество городов N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог между городами: положительное число означает расстояние между городами, ноль говорит о том, что дороги нет.
Выходные данные
Программа должна вывести все кратчайшие маршруты между всеми городами в следующем формате:
(1->3): 1 2 3 (23)
Сначала выводятся номера начального и конечного города (в скобках), затем – последовательность номеров городов, составляющая оптимальный маршрут, затем (в скобках) длина этого маршрута. Если между какими-то городами нет дороги, нужно вывести число 0.
|
Ввод |
Вывод |
|
4
0 0 0 0
0 0 2 1
0 2 0 4
0 1 4 0
|
(1,2): 0
(1,3): 0
(1,4): 0
(2,3): 2 3 (2)
(2,4): 2 4 (1)
(3,4): 3 2 4 (3)
|