Областная олимпиада по информатике 1997/1998 г.
Тур II, Задача 3. "Дорожная карта"
Дорожная карта представлена в ЭВМ двумерным массивом С размером NxN, в котором элемент
C(i,j) равен или длине дороги между городами i и j, или -1, если города i и j не соединены дорогой напрямую.
Составить алгоритм и написать программу, в которой на запрос “маршрут из i в j?” выдается последовательность номеров городов
(i, i1, i2 ..., ik, j) такая, что маршрут из города i в j, проходящий последовательно через
города i1, i2 ...,ik, является наикратейшим. В случае если города i и j не связаны дорогами,
выдается сообщение об отсутствии маршрута.
Основные идеи решения