В полутемной комнате Милан сел за стол и начал думать о возможных последствиях ядерной катастрофы в своем городе. Поскольку Милан - мэр города, он очень хорошо знаком с такими событиями.
А именно, он знает, что в его городе живет ровно \(N\) человек и каждый житель живет в своем собственном доме. Между \(M\) парами домов есть дороги, и для каждой дороги известно, сколько времени потребуется для ее прохождения. Наконец, Милан знает, в каких \(K\) домах есть атомные укрытия и сколько людей помещается в каждое укрытие. Учитывая все это, у Милана возникает следующий вопрос: «Сколько времени нужно, чтобы эвакуировать всех жителей города?»
Помогите Милану ответить на этот вопрос.
Конечно, эвакуация означает, что каждый житель попадает в какое-то атомное убежище. Можно предположить, что жители двигаются оптимально (по кратчайшему пути) и что несколько человек могут двигаться по одной дороге одновременно, возможно в разных направлениях. Также можно считать, что между любыми двумя домами есть хотя бы один путь, проходящий по дорогам.
Первая строка содержит натуральные числа N \((1 \le N \le 100000)\), \(M\) \((1 \le M \le 300000)\) и \(K\) \((1 \le K \le 17)\), которые обозначают количество жителей, количество дорог и количество атомных укрытий. Дома пронумерованы числами от \(1\) до \(N\).
В каждой из следующих \(M\) строк даны три натуральных числа \(A\), \(B\) \((1 \le A, B \le N, A \neq B)\) и \(C\) \((1 \le C \le 10^9)\), которые обозначают, что между домами с номерами \(A\) и \(B\) есть дорога, для прохождения которой требуется \(C\) единиц времени.
В каждой из следующих \(K\) строк даны два натуральных числа \(X\) \((1 \le X \le N)\) и \(Y\) \((1 \le Y \le 10^9)\), которые обозначают, что в доме с номером \(X\) есть атомное убежище, где может быть укрыто максимум \(Y\) людей.
Общая вместимость всех укрытий больше или равна \(N\).
В единственной строке выведите минимальное время, необходимое для эвакуации всех жителей города.
В задаче 3 подгруппы:
5 5 2 1 2 1 1 3 3 2 3 4 3 4 1 4 5 1 1 10 4 2
3
7 8 3 1 2 5 2 3 3 3 4 5 1 4 1 4 5 7 5 6 2 6 7 1 4 7 4 3 3 7 3 6 2
5
Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.
Она организована как подвешенное за вершину 0 дерево из \(n\) (\(1 \le n \le 20000\)) вершин, каждая из которых требует цифру от \(0\) до \(9\). Вершины пронумерованы от \(0\) до \(n - 1\).
Единственная информация, которой владеют коровы – что определённые последовательности длины \(5\) не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.
По заданным \(m\) (\(0 \le m \le 50000\)) последовательностям длины \(5\), вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.
Вы должны выводить свой ответ по модулю \(1234567\).
Первая строка ввода содержит два разделённых пробелом целых числа, \(n\) и \(m\) (\(1 \le n \le 20000, 0 \le m \le 50000\)) - количество вершин в дереве и количество запрещённых последовательностей соответственно.
В последующих \(i\) строках находится описание дерева. Строка \(i + 1\) содержит одно целое число \(p[i]\), означающее родителя вершины \(i\) в дереве (\(0 \le p[i] \lt i\)).
В последующих \(m\) строках находится описание запрещённых последовательностей. Строка \(n + i\) содержит два целых числа \(v_i\) и \(s_i\), разделенные пробелом - стартовую вершину последовательности, и строку из \(5\) цифр, которая не встретится в шифре начиная с вершины \(v_i\) если двигаться вверх по дереву (\(0 \le v_i \lt n\)) соответственно.
Гарантируется, что корень дерева находится не менее чем в 4 шагах от \(v_i\).
Выведите единственное целое число – количество неподходящих конфигураций цифр по модулю \(1234567\).
Подзадача 1 (10 баллов): \(1 \le n \le 15, 0 \le m \le 15\)
Подзадача 2 (15 баллов): \(1 \le n \le 1000, 0 \le m \le 2000\)
Подзадача 3 (20 баллов): \(1 \le n \le 1000, 0 \le m \le 50000\)
Подзадача 4 (55 баллов): \(1 \le n \le 20000, 0 \le m \le 50000\)
6 2 0 1 2 3 3 4 01234 5 91234
19
Поздравляем! Вас наняли управляющим одного крупного завода по производству чего-то очень важного. На вашем заводе есть \(n\) рабочих и \(n\) станков. Каждый рабочий умеет работать на каких-то станках, а на каких-то не умеет. К счастью, вы можете отправить какого-то рабочего на курсы повышения квалификации, чтобы он научился работать на каком-то станке, заплатив за это 1 тугрик. Нет никаких ограничений по тому, кого и сколько раз отправлять на курсы. У ваших работников также очень хорошая память, поэтому если они умели или научились работать на каком-то станке, то уже никогда не забудут, как это делать.
Но не все так радужно. Из-за кризиса сократили всех других менеджеров, поэтому рабочие сами определяют, за каким станком им работать в определенный день. Рабочие могут прийти на работу в случайном порядке. Когда рабочий пришел на работу он может выбрать любой еще не занятый станок, на котором умеет работать, и сядет за него. Если же такого не нашлось, то он расстроится и уйдет домой, а ваш завод понесет убытки. Так, если у вас было два рабочих, первый из которых умел работать на 1 и 2 станке, а второй только на первом, то если первый пришел на работу раньше и занял первый станок, то ваш завод понесет убытки.
Ваша задача в том, чтобы, потратив наименьшее кол-во тугриков на обучение сотрудников, сделать так, чтобы в каждый из дней все рабочие работали, а каждый станок был занят независимо от того, в каком порядке придут рабочие и какие станки они выберут.
В первой строке задано число \(1 \le n \le 25\) - кол-во рабочих и кол-во станков. Каждая из следующих строк содержит информацию об умениях рабочих. \(i+1\)-я строка ввода содержит строку \(s_i\), где \(s_{i,j} = 1\), если \(i\) рабочий умеет работать за \(j\)-м станком и 0 в обратном случае.
Выведите одно число - минимальное кол-во денег, которое вы можете потратить.
Подзадача 1(15 баллов) \(1 \le n \le 3\)
Подзадача 2(45 баллов) \(1 \le n \le 10\)
Подзадача 3(40 баллов) нет дополнительных ограничений
2 11 10
1
2 10 00
1
3 000 110 000
3