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