13. Путь в графе

Не решаласьЛёгкая

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

Формат ввода

Первым на вход поступает число N – количество вершин в графе (1 \le N \le 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

Формат вывода

Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.

Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.

Ограничения

Ограничение времени

1 с

Ограничение памяти

64 МБ

Пример 1

Ввод
10
0 1 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 0
5 4
Вывод
2
5 2 4

Теги

Нужно войти, чтобы отправить решение.Войти
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
/*
Для чтения входных данных необходимо получить их
из стандартного потока ввода (stdin).
Данные во входном потоке соответствуют описанному
в условии формату. Обычно входные данные состоят
из нескольких строк.

Можно использовать несколько функций для чтения из stdin:
* scanf() -- читает данные из потока;
* fgets() -- читает строку из потока;
* gets() -- читает строку из потока до символа '\n'.

Чтобы прочитать из строки стандартного потока:
* число -- int var; scanf("%d", &var);
* строку -- char svar[100]; scanf("%s", svar);
* массив чисел известной длины --
int len; scanf("%d", &len);
int* arr = (int*) malloc(len * sizeof(int));
for (int i = 0; i < len; ++i)
scanf("%d", &arr[i]);
* последовательность слов до конца файла --
char word[100];
while (scanf("%s", word) == 1) {
// do something with word
}

Чтобы вывести результат в стандартный поток вывода (stdout),
можно использовать функцию printf().

Возможное решение задачи "Вычислите сумму A+B":


int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
*/

return 0;
}