|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
17.02.2023, 12:13 | #1 |
Новичок
Джуниор
Регистрация: 12.02.2023
Сообщений: 1
|
Кратчайший путь в невзвешенном графе
Кратчайший путь в невзвешенном графе
ограничение по времени на тест1 секунда ограничение по памяти на тест256 мегабайт вводстандартный ввод выводстандартный вывод Дан ориентированный невзвешенный граф. Также даны стартовая и конечная вершина. Найдите и выведите кратчайший путь между этими двум вершинами. Входные данные В первой строке даны n и m — число вершин и ребер в графе (1≤n≤105,0≤m≤2⋅105). В следующих m строках идут пары чисел, задающие ребра. В последней строке даны s и t — номера стартовой и конечной вершины (1≤s,t≤n,s≠t). Выходные данные Если пути не существует, выведите «-1» без кавычек. Иначе в первой строке выведите длину кратчайшего пути, а в следующей — вершины пути, включая стартовую и конечную. Пример входные данныеСкопировать 5 5 1 2 2 3 3 4 1 5 5 4 1 4 выходные данныеСкопировать 2 1 5 4 |
19.02.2023, 19:25 | #2 |
Форумчанин
Регистрация: 26.10.2022
Сообщений: 119
|
Так это получается просто поиск в ширину. На C++ можно так:
Код:
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Кратчайший путь | ILovePascal | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 11.12.2013 12:26 |
(с++) Кратчайший путь в графе | Uefa | Помощь студентам | 15 | 04.12.2013 15:50 |
Кратчайший путь Delphi | zzzzz | Помощь студентам | 1 | 27.06.2012 07:39 |
Кратчайший путь к точке | W0LF | Общие вопросы Delphi | 3 | 17.05.2011 15:40 |