Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
#1

К-ый путь в графе(ДП) - C++

12.12.2012, 22:32. Просмотров 691. Ответов 1
Метки нет (Все метки)

Здраствуйте! Прошу Вас помоч с задачной на ДП, думаю над ней достаточно долго, но ничего в голову путного не приходит.
Вот условие:

К-ый путь

ограничение времени на тест: 0.5 сек.


Дан ациклический ориентированный граф. Упорядочив все пути из вершины 1 лексикографически (то есть сначала по первой вершине в пути, затем по второй и т.д.). Надо вывести K-ый путь.

Входные данные
В первой строке записаны 3 натуральных числа N, M, K (2 <= N <= 10000; 0 <= M <= 100000), где N количество вершин графа, а M количество ребер. Далее в M строках содержатся описания дуг графа (парами номеров, соединяемых вершин). Гарантируется, что число путей из вершины 1 помещается в тип int64, и число K не превосходит этого количества.
Граф может содержать кратные (повторяющиеся) дуги. Пути проходящие через одну последовательность вершин, но через разные дуги графа, следует считать различными (см. тест 2).

Выходные данные
Выведите К-ый в лексикографическом порядке путь из вершины 1. Вершины в пути разделяйте пробелами.

Пример

Ввод
Test #1
5 10 17
1 4
4 5
3 5
1 2
1 2
3 4
2 3
1 5
2 4
1 3

Test #2
3 3 3
1 2
2 3
1 2

Вывод
Test #1
1 3 4

Test #2
1 2
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2012, 22:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос К-ый путь в графе(ДП) (C++):

Длиннейший путь в графе - C++
Дан ориентированный граф без циклов. Требуется найти в нем длиннейший путь Входные данные 5 5 1 2 2 3 3 4 3 5 1 5 ...

Кратчайший путь в графе. - C++
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь из вершины s в вершину t. ...

Циклический путь в графе - C++
Задача стоит так: &quot;определить самый длинный (по весу) циклический путь в этом графе&quot; граф неориентированный, взвешенный, связан, задаеться...

Найдите кратчайший путь в графе - C++
Создайте граф согласно своего варианта в среде С + +, длины путей задайте самостоятельно, найдите кратчайший путь в графе, используя...

Кратчайший путь в графе(Рекурсия) - C++
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под...

Найти максимальный путь в графе - C++
Аллаху акбар, парни. есть задача, необходимо построить такой многоугольник(не обязательно выпуклый) с вершинами в заданном на плоскости...

1
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
14.12.2012, 15:27  [ТС] #2
Помогите Пожалуйста!!!!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2012, 15:27
Привет! Вот еще темы с ответами:

Как найти НЕ Кратчайший путь в графе ? - C++
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

Найти такую вершину в графе, что любой путь из a в b будет проходить через неё - C++
Есть задача, бьюсь над ней уже третий день. Мне дают неориентированный граф, не содержащий петель и кратных ребер. Также мне дают некоторое...

Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами - C++
Ребята день добрый. Задание у меня вот такое: Используя метод поиска в ширину, найти и вывести путь в ориентированном графе между...

Путь в графе - Delphi
Не могу понять почему выдает ошибку! код procedure TForm1.FormActivate(Sender: TObject); var i:integer; begin for i:=1...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.