Форум программистов, компьютерный форум CyberForum.ru

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

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

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

12.12.2012, 22:32. Просмотров 633. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2012, 22:32     К-ый путь в графе(ДП)
Посмотрите здесь:

C++ минимальные расстояния на графе
Поиск на графе C++
Кратчайший путь в графе. C++
Расстояние на графе C++
C++ Поиск в ширину на графе
Кратчайший путь в графе(Рекурсия) C++
Поиск Ф-циклов в графе C++
Найдите кратчайший путь в графе C++
Построение контура в графе C++
Циклический путь в графе C++
Пути на графе C++
C++ Как найти НЕ Кратчайший путь в графе ?

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
14.12.2012, 15:27  [ТС]     К-ый путь в графе(ДП) #2
Помогите Пожалуйста!!!!
Yandex
Объявления
14.12.2012, 15:27     К-ый путь в графе(ДП)
Ответ Создать тему
Опции темы

Текущее время: 05:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru