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

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

Восстановить пароль Регистрация
 
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 42
07.09.2014, 07:15     Задача "Метки колдунов" #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

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

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

C++ Дан текст, хранящийся в текстовом файле f, каждый символ которого может быть малой буквой, цифрой или одним из знаков "+", "-", "*".
Что означают команды "fun", "my_max", "my_min" в C++? C++
Написать программу, которая запрашивает у пользователя номер дня недели и выводит одно из сообщений: "Рабочий день","Суббота" или "Воскресенье" C++
C++ Написать программу которaя запрашиваeт у пользователя номер дня недели, затем выводит одно из сообщений "рабочий день", "суббота", "воскресенье"
Error C2361: пропуск инициализации "Height" из-за метки "default" C++
C++ Как отключить автоматическое добавление "_" "@" "number" к имени экстернального метода?
На C++ в строке после символа - "+" поставить символ "*" и посчитать сколько "+" C++
Visual Studio не читает операторы, что начинаются на "glu" ("gluBuild2DMipmaps", "gluPerspective") C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Andrej
07.09.2014, 22:45     Задача "Метки колдунов"
  #2

Не по теме:

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

Yandex
Объявления
07.09.2014, 22:45     Задача "Метки колдунов"
Ответ Создать тему
Опции темы

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