Олимпиады по программированию

olympiads.ru

Дистанционные семинары
Оглавление
Как пользоваться
Система проверки задач
Регистрация, изменение настроек
Страница сдачи решений
Результаты
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Задача 05-1. Путь

Имя входного файла input.txt
Имя выходного файла output.txt
Максимальное время работы на одном тесте: 5 секунд

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Формат входных данных
Во входном файле записано сначала число N - количество вершин в графе (1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.

Формат выходных данных
В выходной файл выведите сначала L - длину кратчайшего пути (количество ребер, которые нужно пройти), а затем L+1 число - путь от одной вершины до другой, заданный своими вершинами. Если пути не существует, выведите одно число -1.

Пример

input.txt output.txt
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
3
3 2 1 5