BFS - обход в ширину




№ 4/6 Путь

Read Theory

Для восстановления кратчайших путей надо завести массив "предков" p[], в котором для каждой вершины хранить номер вершины, по которой мы попали в эту вершину.

Task
Time limit: 1000 ms,
Memory limit: 32 Mb

В неориентированном графе требуется найти минимальный путь между 
двумя вершинами. 
 
Входные данные
Во входном файле записано сначала число N - количество вершин в графе
(1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра,
1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной.
 
Выходные данные
В выходной файл выведите сначала L - длину пути (количество ребер, которые
нужно пройти). А затем выведите L+1 число - вершины в порядке следования
вдоль этого пути.
Если пути не существует, выведите одно число -1.
 
Пример входного файла
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
 

Auto CHOOSE THE PROGRAMMING NECESSARY LANGUAGE!
Attach the program source file:
or enter the source code in the language:

Rules for designing programs and a list of errors during automatic task verification
           

Results:
©2009 - 2019 SilverTests.ru/en

Education

Quizes
Problems
Courses

My Account

Register
Sign

About us

Contacts
Rules