Задача на графы

Тема: Графы

Задача:

Во время очередных своих приключений Индиана Джонс нашел гробницу древних индейцев, в
которой по легенде были спрятаны огромные сокровища. Гробница представляла собой сеть комнат
и переходов, в каждом из которых, естественно, была смертоносная ловушка для защиты сокровищ. В
некоторых комнатах находились сундуки с различными сокровищами, в других лишь мелкие
побрякушки.
К счастью, Индиана Джонс выторговал у старого индейца в резервации подробную карту комнат и
переходов гробницы. В карте указано, где и какие именно сокровища нужно искать, а также
перечислены все ловушки, расположенные в переходах.
Индеец также подарил нашему герою магический амулет, который сможет защитить его от ловушек.
У амулета есть заряд, после того, как он спасает от очередной ловушки, заряд уменьшается. Разные
ловушки уменьшают заряд на разную величину, но в карте эти величины указаны.
Единственным условием, которое поставил индеец, было то, что Индиана Джонс заберет лишь одно
сокровище. Как только он возьмет его в руки, все ловушки отключатся, и он сможет спокойно выйти
из гробницы.
Естественно, Индиана Джонс был знаком с теорией графов. С ее помощью он без труда добрался до
самого ценного (насколько позволял заряд амулета) сокровища и вынес его из гробницы.
Вам необходимо написать программу, которая по заданной карте и заряду амулета возвращает
стоимость сокровища, которое вынес из гробницы Индиана Джонс.
Не забывайте, что Индиана Джонс всегда торопится, а переходы в подземелье существуют совсем не
между каждой парой комнат. Стоит учитывать это для реализации наиболее эффективного
алгоритма.
Формат входных данных:
В первой строке входного файла записаны три значения:
P N M – заряд амулета; количество комнат; количество переходов;
В следующих M строках описаны переходы и ловушки в формате:
from to value – номер комнаты, откуда идет переход; номер комнаты, куда идет переход; значение,
на которое ослабляет амулет ловушка из этого перехода;
В следующих N строках записаны стоимости сокровищ, находящихся в соответствующих комнатах. (kая строка соответствует k-ой комнате)
Считать, что начальная комната имеет номер 0.
Формат выходных данных:
В выходной файл необходимо записать стоимость сокровища, которое вынес из гробницы Индиана
Джонс.

Примеры входных и выходных данных в приложенном файле

Вложения

Задача.pdf (177.3 Кб, 1 просмотров)

0

Сообщение от Нейкон сделайте одну несложную задачу

Но очень гордую задачу.

0

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

0

Сообщение от Нейкон сделайте одну несложную задачу)

Я не осилил условие даже до половины. Вайна и мир, бть.

0

Verevkin, ты не любишь приключения Индиана Джонса?

0

Сообщение от Croessmah ты не любишь приключения Индиана Джонса?

Не стоит мешать кино и литературу с точными науками. Это сильно затрудняет выполнение задачи.

0

Индиана Джонс идёт за сокровищами в гробницу. Выторговал подробную карту комнат и
переходов гробницы. В карте указано, где и какие именно сокровища нужно искать, а также
перечислены все ловушки, расположенные в переходах.
У нашего героя также есть магический амулет, который сможет защитить его от ловушек.
У амулета есть заряд, после того, как он спасает от очередной ловушки, заряд уменьшается. Разные
ловушки уменьшают заряд на разную величину, но в карте эти величины указаны.
Единственным условием было то, что Индиана Джонс заберет лишь одно
сокровище. Как только он возьмет его в руки, все ловушки отключатся, и он сможет спокойно выйти
из гробницы.
Естественно, Индиана Джонс был знаком с теорией графов. С ее помощью он без труда добрался до
самого ценного (насколько позволял заряд амулета) сокровища и вынес его из гробницы.

ЗАДАЧА:
Вам необходимо написать программу, которая по заданной карте и заряду амулета возвращает
стоимость сокровища, которое вынес из гробницы Индиана Джонс.
Не забывайте, что Индиана Джонс всегда торопится, а переходы в подземелье существуют совсем не
между каждой парой комнат. Стоит учитывать это для реализации наиболее эффективного
алгоритма.

Формат входных данных:
В первой строке входного файла записаны три значения:
P N M – заряд амулета; количество комнат; количество переходов;
В следующих M строках описаны переходы и ловушки в формате:
from to value – номер комнаты, откуда идет переход; номер комнаты, куда идет переход; значение,
на которое ослабляет амулет ловушка из этого перехода;
В следующих N строках записаны стоимости сокровищ, находящихся в соответствующих комнатах. (kая строка соответствует k-ой комнате)
Считать, что начальная комната имеет номер 0.
Формат выходных данных:
В выходной файл необходимо записать стоимость сокровища, которое вынес из гробницы Индиана
Джонс.

Примеры входных и выходных данных в приложенном файле

Вложения

Задача.pdf (177.3 Кб, 0 просмотров)

0

Думаю, что так нормально

0