Бобр из Бобруйска строит плотину. Для постройки плотины Бобр таскает бревна из леса. В лесу есть $z$ деревьев. Из одного дерева получается одно бревно. Из $i$-го дерева получается бревно размеров $1$ на $z_i$. Брёвна резать нельзя. На то, чтобы срубить $i$-ое дерево уходит $t_i$ секунд. Плотина должна иметь 3 слоя и каждый слой длины $n$. Деревья находятся в лесу. Расстояние между плотиной и $i$-ым деревом равно $q_i$. Брёвна можно класть только горизонтально. Расстояние между деревьями задано списком рёбер с весами, где вес — количество метров между деревьями (граф не обязательно полный, но неориентированный, ходить бобру можно только по рёбрам). Бобр за раз может перенести не более 2 — ух брёвен. Его скорость передвижения — 1 метр в секунду. Нумерация с единицы.↵
↵
Считайте что размер входных данных достаточно большой, и перебором эта задача не решается. Скиньте решения, я посмотрю на асимптотику и впишу размеры данных(так как у меня решения нет).↵
В первой строке задано $z$ — количество деревьев.↵
Во второй строке список длины $z$ — длины брёвен которые получается из деревьев.↵
В третьей строке список длины $z$ — время на сгрызание деревьев.↵
В четвертой строке вводится список длины $q$ — расстояние от платины до деревьев.↵
В пятой строке вводится $n$ — длина слоёв.↵
В шестой строке вводится $m$ — количество путей между деревьев.↵
В следующих $m$ строках вводится по три числа: 2 номера деревьев и расстояние между ними в метрах.↵
↵
Выведите w строк, в каждой строке выведите номера деревьев которые войдут в этот слой, бобр должен это сделать это за минимальное возможное время.↵
Если плотину построить нельзя выведите -1.↵
↵
Это вообще решабельно?↵
Если нет, то напишите об этом.
↵
Считайте что размер входных данных достаточно большой, и перебором эта задача не решается. Скиньте решения, я посмотрю на асимптотику и впишу размеры данных(так как у меня решения нет).↵
В первой строке задано $z$ — количество деревьев.↵
Во второй строке список длины $z$ — длины брёвен которые получается из деревьев.↵
В третьей строке список длины $z$ — время на сгрызание деревьев.↵
В четвертой строке вводится список длины $q$ — расстояние от платины до деревьев.↵
В пятой строке вводится $n$ — длина слоёв.↵
В шестой строке вводится $m$ — количество путей между деревьев.↵
В следующих $m$ строках вводится по три числа: 2 номера деревьев и расстояние между ними в метрах.↵
↵
Выведите w строк, в каждой строке выведите номера деревьев которые войдут в этот слой, бобр должен это сделать это за минимальное возможное время.↵
Если плотину построить нельзя выведите -1.↵
↵
Это вообще решабельно?↵
Если нет, то напишите об этом.
