- Описание
- Отправленные решения
13. Путь в графе
В неориентированном графе требуется найти минимальный путь между двумя вершинами.
Формат ввода
Первым на вход поступает число N – количество вершин в графе (1 N 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;
}