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

Графы и алгоритм Левита - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Строку в обратную польскую запись http://www.cyberforum.ru/cpp-beginners/thread700136.html
Подскажите, как представить выражение из строки в обратную польскую запись и потом посчитать? Наверное есть уже готовые алгоритмы...
C++ Ошибка при компиляции Всем здрасте , я тут новенький , при компиляции выходит ошибка , вот отрывочек : 1> Для всех выходных данных обновления не требуется. 1>LINK : fatal error LNK1123: сбой при преобразовании в COFF: файл недопустим или поврежден 1>СБОЙ построения. 1>Затраченное время: 00:00:00.12 ========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ========== Вот кодишко :... http://www.cyberforum.ru/cpp-beginners/thread700110.html
C++ Контейнер list, вывод содержимого в заданном порядке
Как с помощью двунаправленных итераторов вывести содержимое списка в таком порядке: первый эл-т,последний,второй эл-т,предпоследний и т.дfor (int ii=0;ii<15;ii++) { my_list.push_back(rand()%20); }
C++ Реализовать шаблонный класс property
Необходимо реализовать шаблонный класс property, реализующийся на С++ станд. средствами вообще не знаю как делать(((
C++ Подтверждение от пользователя http://www.cyberforum.ru/cpp-beginners/thread700058.html
Например, у меня есть цикл на повтор программы char otvet; do { cout<<"Желаете ли Вы повторить свое решение? 1/0 "; cin>>otvet; }while(otvet=='1')
C++ Помоги сделать по информатике задачу, что-то у меня ничего не выходит http://cs402725.userapi.com/v402725339/3f40/qf8x7sAxJhs.jpg подробнее

Показать сообщение отдельно
_Prof_
 Аватар для _Prof_
1 / 1 / 0
Регистрация: 09.10.2011
Сообщений: 6
17.11.2012, 19:20     Графы и алгоритм Левита
Доброго времени суток, ув. форумчане! С ровного места возникла проблема: препод дал задачу, но по такому материалу что ещё не проходили, сказал если до воскресения не сделаем- завалит.
Знаю только что нужно делать на графах и алгоритме Левита (или дейкстры), но ни того ни другого не проходили, тоесть знаний по этому у меня покачто ноль. Обьясните пожалуйста как это реализовать.

Условие:

Кликните здесь для просмотра всего текста
Кому из вас не известен знаменитый мультфильм режиссеров Криса Уэйдж и Карлоса Сайдана «Ледниковый период»? Говорят, что после «Ледникового период-2» выйдет «Ледниковый период-3» и в перспективе начнутся работы над созданием нового катастрофического мультфильма «Глобальное потепление-1».

Изюминку сюжета этого фильма составляет момент, когда ненасытная белочка Скрэт попала в Долину Желудей. Помимо огромных пищевых запасов, Скрэт поразила сама местность. Вся долина - это определенное количество холмов, представляют собой полусферы разных радиусов. Конечно, эти симпатичные бугорки пестрят от обилия желудей. Все было бы для Скрэт замечательно, если бы человек своей техногенной деятельностью не спровоцировала глобальное потепление. Очередная катастрофа застала белочку посреди этой широкой долины. Долину начало быстро затапливать и Скрэт в панике прыгала с одного бугорка на другой, ища спасения. Белка, благодаря большим запасам желудей было достаточно энергии чтобы прыгать на любой бугорок, находившийся не далее, чем L метров от бугорка, на котором находилась она сама. Расстояние между бугорками - это расстояние между центрами полусфер независимо от их радиуса. За каждую минуту вода поднималась на высоту H метров. Итак, высота видимой из воды части полусферы также уменьшались на H м в каждую минуту. Скрэт видела, что один за другим исчезают под водой спасательные островки земли. Для того чтобы спастись, она должна быстро добраться крупнейшего бугорка (остривка. Помогите Скрэт найти спасительный путь к самому островка, если за 1 минуту может осуществить только один прыжок. Белочка не может прыгать на островок, сравнялся с поверхностью воды, но всегда успевает покинуть островок, который должен быть затоплен в течение следующей минуты.

Входящие данные: В первой строке входного файла находятся три целых числа N, L, H (2 <= N <= 100, 0 <L <= 1000, 0 <= H <100). В следующих N строках дано по три целых числа Xi, Yi, Ri ((10000 <= Xi, Yi <= 10000, H <Ri <= 10000). Скрэт в начальный момент времени находится на первом острове. Нижние части островков могут перекрываться, но никакие два центра не совпадают.

Исходящие данные: В случае наличия спасительного пути к крупнейшего острова в первую строку выходного файла вывести наименьшее количество прыжков Скрэт, а во вторую строку через пробел вывести номера островов, на которые она должна последовательно прыгать. Если есть несколько самых крупных островов - вывести путь к острову с минимальным номером. В случае отсутствия спасительного пути в единственную строку выходного файла вывести сообщение «The life is fine» без кавычек.


Примеры входящих и исходящих данных:
Кликните здесь для просмотра всего текста

Пример 1:

Входящие:

6 4 1
1 1 1
0 3 2
3 5 1
6 6 4
4 0 2
6 2 3

Исходящие:

3
5 6 4

Пример 2:

Входящие:

2 10 10
0 0 5
10 10 20

Исходящие:

The life is fine


Добавлено через 6 часов 14 минут
Пробовал релизовать это на поиске в глубину, завис ещё на построении графа...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 20:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru