Задача №113760. Мониторинг труб
Газораспределительная система одного региона устроена следующим образом. Она содержит n узлов, пронумерованных от 1 до n , некоторые узлы соединены односторонними трубами. Узел с номером 1 соответствует центральному газохранилищу. Система узлов описывается числами от p 2 , p 3 , ..., p n . Для всех i от 2 до n узел с номером p i соединен односторонней трубой с узлом i , газ по этой трубе передается от узла p i к узлу i . Известно, что возможно доставить газ по трубам от центрального газохранилища до любого узла системы (возможно, с использованием промежуточных узлов). В системе используются трубы различных типов, тип трубы обозначается буквой английского алфавита от «a» до «z». Труба, соединяющая узел p i с узлом i , имеет тип c i .
Для проверки качества труб используется специальный робот. Он помещается в систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по которой он перемещается. Робот может перемещаться по трубам только в том же направлении, в котором по трубе передается газ. Совершив одно или несколько перемещений по трубам между узлами, робот извлекается из системы труб.
Каждый запуск робота должен соответствовать одной из m заданных спецификаций , пронумерованных от 1 до m . Спецификация с номером t представляет собой строку s t , состоящую из строчных букв английского алфавита. Запуск соответствует спецификации s t , если количество перемещений робота по трубам во время запуска совпадает с длиной s t , и для всех j от 1 до длины s t на j -м шаге робот перемещается по трубе, тип которой совпадает с s t [ j ] —символом на позиции j в спецификации.
Если запуск робота соответствует спецификации с номером t , то стоимость этого запуска составляет w t . Оператору системы необходимо проверить все трубы, для этого можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была минимальна. Одну и ту же трубу можно проверять несколько раз.
Требуется написать программу, которая по описанию системы труб и списку спецификаций определяет минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены, а также список необходимых для этого запусков (по требованию)
В первой строке входных данных находятся три целых числа n , m и t — количество узлов системы труб, количество спецификаций запусков робота и параметр, указывающий, требуется ли вывести список запусков робота или только их минимальную суммарную стоимость ( 1 ≤ n ≤ 500 , 0 ≤ m ≤ 10 5 , t равно 0 или 1 ).
В последующих ( n – 1 ) строках содержится информация о трубах, ( i – 1 )-я из этих строк содержит разделенные пробелом значения p i и c i , где p i — целое число, задающее номер узла, из которого ведет труба в i -й узел, а c i — строчная буква английского алфавита, задающая тип этой трубы ( 1 ≤ p i ≤ i – 1 ).
В последующих m строках содержится информация о спецификациях, i -я из этих строк содержит разделенные пробелом целое число w i — стоимость запуска робота в соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита строку s i — саму спецификацию ( 1 ≤ w i ≤ 10 9 ). Суммарная длина строк s i не превышает 10 6 .
Первая строка выходных данных должна содержать одно число — минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены. Если проверить все трубы невозможно, требуется вывести « -1 ».
Если t = 0 , то больше ничего выводить не требуется.
Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний запусков робота. В этом случае вторая строка выходных данных должна содержать число k — количество запусков робота, которое необходимо выполнить для проверки труб. В следующих k строках необходимо вывести по три целых числа a i , b i и c i — номер узла, в котором начинается запуск, номер узла, в котором заканчивается запуск, и номер спецификации, которой соответствует запуск.
Если оптимальных способов проверки несколько, требуется вывести любой из них.
Система труб, заданная во втором примере входных данных, и оптимальный способ проверки всех труб для этого случая приведены на рисунке ниже.
- трубу можно проверять несколько раз, так в приведенном примере дважды проверена труба из узла 2 в узел 3 ;
- одну и ту же спецификацию разрешается использовать несколько раз, в приведенном примере вторая спецификация используется дважды, для проверки труб из узла 1 в узел 6 и из узла 6 в узел 7 ;
- робот может перемещаться по трубам только в том же направлении, по которому по трубе передается газ, спецификацию ab нельзя использовать для проверки труб по маршруту 2→1→6 , так как робот не может переместиться из узла 2 в узел 1 .
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
3 3 0 1 a 2 b 3 a 4 b 2 a
6
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 1 6 2 6 7 2 2 5 3