Задача №112651. Кратчайший маршрут
Принц Винсент получил карту дорог страны Лимония. Теперь ему требуется определить кратчайший маршрут из города A , где он находится, в город B , где его ждёт невеста. Помогите Винсенту – напишите программу, которая решает эту задачу.
В первой строке вводится количество городов N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог между городами: положительное число означает расстояние между городами, ноль говорит о том, что дороги нет. В следующей строке вводятся номера начальной и конечной точек (городов), A и B . Нумерация городов начинается с единицы.
Программа должна вывести в первой строчке длину кратчайшего маршрута. Во второй строчке выводится последовательность городов, начиная с города A и заканчивая городом B , через которые нужно ехать принцу. Если дороги между заданными городами вообще нет, нужно вывести число 0.
6 0 2 4 0 0 0 2 0 1 0 0 0 4 1 0 2 6 0 0 0 2 0 4 1 0 0 6 4 0 1 0 0 0 1 1 0 3 5
4 3 4 6 5