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

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

Войти
Регистрация
Восстановить пароль
 
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
#1

Задача "Метки колдунов" - C++

07.09.2014, 07:15. Просмотров 275. Ответов 1
Метки нет (Все метки)

Всем доброго времени суток!

Не приходят идеи по решению задачи:

Задача 3. Метки колдунов
В банке гоблинов есть сеть тоннелей, ведущих на поверхность из их
подземных хранилищ. Схематичное изображение одной из таких сетей
приведено на рисунке справа. Внизу рисунка отмечен подвал,
обозначенный буквой A, поверхность отмечена буквой F. Другие буквы
обозначают площадки, на которых пересекаются тоннели. Тоннели,
ведущие на поверхность от площадки, имеют направление наверх
рисунка. Так как это двумерная схема трехмерной сети тоннелей, то
тоннели, пересекающиеся на рисунке, но не отмеченные буквами, на
самом деле не пересекаются. Например, тоннель BD не пересекается с
тоннелем CE.
Перед группой колдунов встала необходимость разработать план прохода через тоннели на
поверхность за минимальное количество времени. Они смогли заранее измерить время
прохождения по каждому тоннелю от одной площадки до другой, это время отмечено на схеме
числами. Но во время бегства у них не будет времени смотреть на карту, и они не хотят оставлять
лишних подсказок своим преследователям. Колдуны решили оставить тайные метки на тоннелях,
метка должна означать, что колдуны должны следовать отмеченным тоннелем. Чтобы их метки не
были раскрыты, нужно оставить их как можно меньше.
На перовом рисунке метки показаны стрелками на тоннелях AB и BC,
от площадки C есть только один тоннель, ведущий на поверхность. Таким
образом, колдун, идущий по меткам к C, достигнет поверхности за время 3
+ 1 + 4 = 8, это минимальное возможное время.
На втором рисунке приведена та же схема, но поставлена только одна
метка, на тоннеле ED. Эта метка не определяет однозначно путь, но
обеспечивает минимальное время достижения поверхности. Колдун от A
может бежать к B или к E. Если он побежит к B, то там нужно выбирать
между двумя тоннелями, но в любом из этих случаев время пути будет
минимальное, равное 8. Маркер на ED нельзя убрать, так как при выборе
пути AECF время будет 2 + 3 + 4 = 9. Таким образом, для гарантии прохождения по пути на
поверхность за минимальное время на данной схеме нужно поставить только одну метку.
Колдуны попросили вас написать программу, которая расставляет метки на схеме.

Входные данные
Первая строка входного файла содержит целое число S – количество схем в файле (1 ≤ S ≤ 5).
Далее идет описание S схем в следующем формате.
Первая строка описания схемы содержит целое число N – количество площадок, включая нижнюю площадку, площадку на поверхности и промежуточные площадки(2 ≤ N ≤ 17).
Далее N строк описывают тоннели, идущие от каждой площадки наверх.
Каждая строка начинается с буквы, обозначающей описываемую площадку, далее идет число U – количество тоннелей, идущих наверх от данной площадки, потом через пробел следуют U пар (буква, время), обозначающих площадку, к которой идет тоннель, и время (целое число, не большее 500), необходимое на его преодоление.
Буквы в начале каждой строки идут в возрастающем порядке, все буквы — прописные латинские, A всегда стартовая точка, и последняя буква всегда площадка на поверхности. Только для последней площадки U всегда равно 0, в остальных случаях 1 ≤ U≤ 6.
Также нужно учитывать следующие ограничения: Колдуны всегда должны идти только по тоннелям, ведущим наверх. Общее количество тоннелей не превышает 35. На поверхность всегда есть путь, занимающий минимальное время и отстоящий не более, чем из 7 тоннелей. Любая промежуточная площадка имеет, по крайней мере, один тоннель, ведущий к ней снизу, и один тоннель, ведущий от нее наверх.
Выходные данные
Вывести S строк, для каждой схемы по строке, содержащей минимальное время пути из подвала на поверхность и минимальное количество меток, необходимое для обеспечения бега колдунов на поверхность за минимальное время.
Пример
input.txt

2
6
A 2 B 3 E 2
B 2 C 1 D 4
C 1 F 4
D 1 F 1
E 2 C 3 D 5
F 0
7
A 3 B 1 C 5 D 4
B 2 C 2 E 5
C 2 E 4 F 3
D 2 C 2 F 3
E 1 G 6
F 1 G 4
G 0

output.txt
8 1
10 3

Кратчайший путь найти не сложно. Сложность возникает при постановке меток. Если подойти рекурсивно, то из данной вершины можно либо поставить метку в в какую-то вершину либо, если все расстояния равны, не ставить метку. Но тогда нужно складывать метки по всем направлениям... вот как это сделать я не могу придумать, т.к. не факт, что если на данной вершине мы получим минимум меток то это будет оптимально...

Если не сложно, подскажите алгоритм с метками...
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.09.2014, 07:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача "Метки колдунов" (C++):

Error C2361: пропуск инициализации "Height" из-за метки "default" - C++
Добрый день! Решила чуть изменить типичный код из учебника - и тут же появилась ошибка компилятора. Код вот такой: #include...

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс "вентилятор" содержащий в себе классы:...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Andrej
07.09.2014, 22:45     Задача "Метки колдунов"
  #2

Не по теме:

слишкам многа букафф

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2014, 22:45
Привет! Вот еще темы с ответами:

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Реализовать структуру "Анкета" с полями "Фамилия", "Пол" и "Адрес" - C++
Здравствуйте. Проходим тему Структуры, не могу понять, как определить количество, само задание: #include <iostream> #include...


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

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

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