|
Мониторинг труб
(Время: 5 сек. Память: 256 Мб Сложность: 72%)
Газораспределительная система одного региона устроена следующим образом. Она содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними трубами. Узел с номером 1 соответствует центральному газохранилищу.
Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до любого узла системы (возможно, с использованием промежуточных узлов). В системе используются трубы различных типов, тип трубы обозначается буквой английского алфавита от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.
Для проверки качества труб используется специальный робот. Он помещается в систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по которой он перемещается. Робот может перемещаться по трубам только в том же направлении, в котором по трубе передается газ. Совершив одно или несколько перемещений по трубам между узлами, робот извлекается из системы труб.
Каждый запуск робота должен соответствовать одной из m заданных спецификаций, пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st, состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st, если количество перемещений робота по трубам во время запуска совпадает с длиной st, и для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с st[j] —символом на позиции j в спецификации.
Если запуск робота соответствует спецификации с номером t, то стоимость этого запуска составляет wt. Оператору системы необходимо проверить все трубы, для этого можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была минимальна. Одну и ту же трубу можно проверять несколько раз.
Требуется написать программу, которая по описанию системы труб и списку спецификаций определяет минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены, а также список необходимых для этого запусков (по требованию).
Входные данные
В первой строке входного файла INPUT.TXT находятся три целых числа n, m и t — количество узлов системы труб, количество спецификаций запусков робота и параметр, указывающий, требуется ли вывести список запусков робота или только их минимальную суммарную стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 105, t равно 0 или 1).
В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита, задающая тип этой трубы (1 ≤ pi ≤ i – 1).
В последующих m строках содержится информация о спецификациях, i-я из этих строк содержит разделенные пробелом целое число wi — стоимость запуска робота в соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита строку si — саму спецификацию (1 ≤ wi ≤ 109). Суммарная длина строк si не превышает 106.
Выходные данные
Первая строка выходного файла OUTPUT.TXT должна содержать одно число – минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены. Если проверить все трубы невозможно, требуется вывести «–1».
Если t = 0, то больше ничего выводить не требуется.
Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний запусков робота. В этом случае вторая строка выходных данных должна содержать число k – количество запусков робота, которое необходимо выполнить для проверки труб. В следующих k строках необходимо вывести по три целых числа ai, bi и ci – номер узла, в котором начинается запуск, номер узла, в котором заканчивается запуск, и номер спецификации, которой соответствует запуск.
Если оптимальных способов проверки несколько, требуется вывести любой из них.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 3 0
1 a
2 b
3 a
4 b
2 a | 6 |
2 | 7 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab | 15
4
1 4 1
2 5 3
1 6 2
6 7 2 |
Пояснение к примеру №2
Система труб, заданная во втором примере входных данных, и оптимальный способ проверки всех труб для этого случая приведены на рисунке ниже.
Необходимо обратить внимание на следующие моменты:
- трубу можно проверять несколько раз, так в приведенном примере дважды проверена труба из узла 2 в узел 3;
- одну и ту же спецификацию разрешается использовать несколько раз, в приведенном примере вторая спецификация используется дважды, для проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;
- робот может перемещаться по трубам только в том же направлении, по которому по трубе передается газ, спецификацию «ab» нельзя использовать для проверки труб по маршруту 2→1→6, так как робот не может переместиться из узла 2 в узел 1.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |