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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Изменения размерности динамического массива http://www.cyberforum.ru/cpp-beginners/thread1252190.html
недавно задался вопросом, а можно как-то изменить размерность динамического массива ну например есть такой массив int n; n=5; int *mas; mas=new int; потом я где-то в программе решил его увеличить и сделать например 6 или 7 ну или еще что, можно как-то это сделать? ну или например уменьшить
C++ Сколькими способами человек может попасть в магазин МАГАЗИН На расстоянии N шагов от магазина стоит человек. Каждую минуту он выбирает, куда сделать шаг: к магазину или в противоположном направлении. Требуется написать программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно K шагов и оказавшись в магазине только после выполнения последнего шага. Входные данные Входной файл INPUT.TXT содержит 2 числа n... http://www.cyberforum.ru/cpp-beginners/thread1252180.html
Скиньте интересные задания по ООП С++ C++
Добрый вечер, Начал изучать ООП - скиньте интересные задания с использованием ООП С++. Книжные задачки перерешал уже.
Класс Rectangle: возвратить значения координат, длины, ширины и площади C++
Реализовать класс Rectangle. Класс должен хранить координаты, а так же длину и ширину прямоугольника. Предусмотреть инициализацию данного класса через конструктор по умолчанию и с помощью координат двух противоположных вершин. Общими должны быть методы, которые возвращают координаты прямоугольника (x1, x2, y1, y2), длину, ширину, площадь, а также методы позволяющие изменять координаты, длину и...
C++ Решение нелинейных уравнений методом простой итерации http://www.cyberforum.ru/cpp-beginners/thread1252158.html
Решение нелинейных уравнений методом простой итерации. Реализовать заданный алгоритм для уравнения , решив уравнение с заданной пользователем точностью.
C++ Перегрузка оператора + в одномерном массиве Требуется сцепить два одномерных массива в один mnog operator+(const mnog &R){ int k = size + R.size; //размер нового массива int r = 0; mnog mnogestvo3(k);//создание объекта (новый массив) for (int i = 0; i < size; i++){ mnogestvo3(r) = m; r++; } for (int i = 0; i < R.size; i++){ подробнее

Показать сообщение отдельно
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 42
07.09.2014, 07:15     Задача "Метки колдунов"
Всем доброго времени суток!

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

Задача 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

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

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