|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 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 |