Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Mashenbka
0 / 0 / 0
Регистрация: 08.11.2015
Сообщений: 1
1

Найти минимальную сумму денег, которую нужно будет потратить, чтобы собрать конструктор

08.11.2015, 18:33. Просмотров 292. Ответов 0
Метки нет (Все метки)

Помогите пожалуйста, а то я уже устала
Помимо математики Георгий любит собирать замки из конструкторов. В магазин завезли n конструкторов. Конструкторы пронумерованы числами от 1 до n.
У Георгия есть 2 способа получить нравящийся конструктор:
1. Купить его. Конструктор с номером i стоит ci рублей;
2. Купить и объединить два конструктора, получив из них другой конструктор. Возможные способы компоновки конструкторов заданы тройками чисел (x, y, z). Купив конструкторы с номерами y и z, можно их объединить и получить один конструктор с номером x. Всего есть m доступных троек (x, y, z)
Георгий ограничен в средствах и просит вас помочь ему найти минимальную сумму денег, которую нужно будет потратить, чтобы собрать конструктор, из которого можно будет построить замок номер 1.
Вход: файл input.txt, в первой строке записаны два целых числа n и m. Во второй строке содержатся n чисел ci – стоимости конструкторов. В следующих m строках содержится по 3 числа xi, yi, zi – это означает, что конструктор номер xi может быть скомпонован из конструкторов yiи zi.
Ограничения: 1≤ n≤ 104, 0≤ m≤ 105, 0 ≤ ci ≤ 109, 1 ≤xi,yi,zi≤ n
Выход: файл output.txt, содержащий единственное число – минимальная сумма денег, которую потратит Георгий.
Примеры:
input.txt output.txt
4 2
8 1 1 3
4 2 3
1 2 4 3
4 2
2 1 1 3
4 2 3
1 2 4 2

Примечание:
В первом тестовом примере, можно купить конструкторы номер 2 и 3, собрать из них детали для конструктора номер 4, затем купить ещё один конструктор номер 2 и собрать из имеющихся конструкторов конструктор номер 1. На это будет затрачено 1+1+1=3 рубля.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.11.2015, 18:33
Ответы с готовыми решениями:

Какую минимальную сумму нужно истратить для покупки N дисков при данных ценах?
Проблема с задачей. Чистые компакт-диски продают в трёх видах упаковок....

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

Найти минимальную сумму строки матрицы
Статическая память. Двумерный массив. Дан массив целых чисел (4х6). Найти...

Найти минимальную сумму элементов строки матрицы
Как найти максимальный элемент в двумерном массиве на языке си в каждом из...

Узнать, какую наименьшую сумму денег Максиму придётся потратить, если он будет отказываться от сдачи
Здравствуйте, помогите с алгоритом, часов 15 думаю ни как придумать не могу....

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2015, 18:33

Способы потратить определенную сумму денег определенными монетами
У Вас А монет по Х рублей и В монет по Y рублей. Можно ли с их помощью...

Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол
Вот такая задачка: В прямоугольной таблице NxM (в каждой клетке которой...

Найти минимальную сумму, заплатив которую игрок может попасть в правый нижний угол
Задача 1413-1413 Ограничение по времени на тест 1 seconds, ограничение по...


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

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

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