В государстве алхимиков есть N населённых пунктов, пронумерованных числами от 1 до N, и M дорог. Населённые пункты бывают двух типов: деревни и города. Кроме того, в государстве есть одна столица (она может располагаться как в городе, так и в деревне). Каждая дорога соединяет два населённых пункта, и для проезда по ней требуется Ti минут. В столице было решено провести 1-ю государственную командную олимпиаду по алхимии. Для этого во все города из столицы были отправлены гонцы (по одному гонцу на город) с информацией про олимпиаду.
Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберётся до своего города. Считается, что гонец во время пути не спит и нигде не задерживается.
Во входном файле сначала записаны 3 числа N, M, K — количество населенных пунктов, количество дорог и количество городов (2N1000, 1M10000, 1KN). Далее записан номер столицы C (1CN). Следующие K чисел задают номера городов. Далее следуют M троек чисел Si, Ei, Ti, описывающих дороги: Si и Ei — номера населенных пунктов, которые соединяет данная дорога, а Ti — время для проезда по ней (1Ti100).
Гарантируется, что до каждого города из столицы можно добраться по дорогам (возможно, через другие населенные пункты).
Выведите в выходной файл K пар чисел: для каждого города должен быть выведен его номер и минимальное время, когда гонец может в нем оказаться (время измеряется в минутах с того момента, как гонцы выехали из столицы). Пары в выходном файле должны быть упорядочены по времени прибытия гонца.
5 4 5 1 1 2 3 4 5 1 2 1 2 3 10 3 4 100 4 5 100
1 0 2 1 3 11 4 111 5 211
5 5 3 1 2 4 5 2 1 1 2 3 10 3 4 100 4 5 100 1 5 1
5 1 2 1 4 101
Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.
В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.
Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.
В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki — количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+…+KL≤100000. Количество этажей в небоскребе не превосходит 1000000.
В выходной файл выведите одно число — минимальную стоимость подъема сейфа.
Группы тестов:
10 1 1 1 1 1 2 3 7
7
10 1 1 3 2 1 2 3 7
9
20 100 0 1 1 2 2 5 7 2 8 17
804
Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (Ai, Bi).
Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (Ai, Bi) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах Ai и Bi и поменять их местами.
Например, если N=5. Тогда изначально Васей выписана последовательность
1 2 3 4 5
Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.
Например, он может последовательно получить следующие последовательности:
2 1 3 4 5 (поменяв числа на 1 и 2 местах)
2 5 3 4 1 (поменяв числа на 2 и 5 местах)
5 2 3 4 1 (поменяв числа на 1 и 2 местах).
Пете не показываются промежуточные последовательности, а выписывается лишь полученная на последнем шаге.
От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).
Напишите программу, которая поможет Пете справиться с этой задачей.
Сначала записано число N (1≤N≤100) – количество чисел в последовательности. Дальше идет N чисел – последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).
Далее идет число P (0≤P≤10000) – количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары – из диапазона от 1 до N).
В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).
В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K – количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.
5 5 2 3 4 1 2 1 2 2 5
YES 3 1 2 2 5 1 2
5 2 3 4 5 1 2 1 2 2 5
NO
Петя с Васей решили поздравить всех своих одноклассниц с Международным Женским Днем. Важной частью любого праздника являются открытки. Купив их достаточно, друзья сели писать пожелания. Подписанные открытки они складывали на специальный стол, расчерченный в квадратную клетку параллельно краям стола так, что длина и ширина его составляли N и M клеток соответственно. По удивительному совпадению каждая открытка была размером точь-в-точь с две клетки стола. Петя настоял на том, чтобы класть подписанные поздравления строго по линиям сетки — горизонтально или вертикально, накрывая одной открыткой ровно две клетки.
По окончанию работы оказалось, что каждая клетка стола накрыта ровно двумя открытками — крайне неудобное расположение для того, чтобы их дарить. К счастью, рядом был еще один такой же стол, поэтому они решили переложить на него половину открыток так, чтобы остальные, оставаясь на своем месте, образовывали ровно один слой — не накладывались друг на друга и полностью покрывали бы стол. Чтобы не нарушать порядка, открытки надо доставать по одной, извлекать очередную разрешается только в случае, если хотя бы одна из ее половинок лежит сверху (то есть эту половинку не накрывает другая открытка).
Поскольку одноклассниц у Пети и Васи довольно много, они обратились за помощью к Вам. Напишите программу, которая подскажет, какие открытки извлекать и в какой последовательности, либо определит, что это невозможно.
В первой строке входного файла записаны два целых числа N и M (1 ≤ N, M ≤ 700) — длина и ширина стола. Гарантируется, что хотя бы одно из N, M четное. Будем считать, что все открытки занумерованы числами от 1 до NM. Следующие 2N строк содержат по M чисел: первые N строк описывают нижний слой, следующие N строк — верхний слой. Число k в i-й строке j-м столбце нижнего или верхнего слоя означает наличие на этой позиции одной из половинок открытки номер k.
Гарантируется, что входные данные корректны, то есть что каждое число 1 до NM встречается ровно два раза, и эти вхождения находятся на соседних позициях, при этом они могут находиться как в одном слое, так и в разных. Кроме того, если две открытки покрывают одни и те же клетки, то одна из них находится обеими половинками снизу, а другая — сверху.
В выходной файл запишите единственное слово NO, если не существует способа извлечь половину открыток нужным образом. В противном случае в первую строку выведите YES, во вторую — последовательность из NM/2 номеров открыток, которые надо достать, в правильном порядке. У каждой из них на момент извлечения хотя бы одна из половинок должна находиться сверху. Если искомых последовательностей несколько, выведите любую из них.
Частичные ограничения
Первая группа состоит из тестов, в которых произведение NM ≤ 24.
Вторая группа состоит из тестов, в которых N, M ≤ 100.
2 2 1 1 3 2 4 2 4 3
YES 4 2
2 3 1 1 4 2 3 4 2 6 5 3 6 5
YES 2 6 5
Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».
Участник соревнований получает маршрутный лист, где указано, какие контрольные пункты и в каком порядке он должен посетить (в каждом пункте участник должен отметиться). При этом участник должен отмечаться в пунктах строго в указанном порядке. Какие-то пункты может потребоваться посетить несколько раз.
Специально по случаю соревнования между контрольными пунктами будут ходить автобусы. Перемещаться от контрольного пункта к контрольному пункту разрешается только на автобусах. При этом можно пользоваться как прямым рейсом, соединяющим контрольные пункты (если он существует), так и добираться с пересадкой через другие контрольные пункты (если это оказывается быстрее или если прямого маршрута вовсе нет), при этом в пересадочных пунктах участник не отмечается.
Известен маршрутный лист участника и расписание движения автобусов. Требуется определить минимальное время, которое понадобится участнику на прохождение маршрута.
Сначала вводится число \(N\) — общее количество контрольных пунктов (2≤\(N\)≤10000).
Далее вводится количество автобусных маршрутов \(K\) (1≤\(K\)≤50000). Далее идет \(K\) описаний автобусных маршрутов.
Каждый маршрут описывается четырьмя числами \(A_i\), \(B_i\), \(C_i\), \(D_i\), которые означают, что каждые \(C_i\) минут (т.е. в моменты времени 0, \(C_i\), 2*\(C_i\), …) автобус выходит от контрольного пункта \(A_i\) и через \(D_i\) минут прибывает к контрольному пункту \(B_i\). Все \(C_i\) и \(D_i\) — натуральные и не превышают 10000.
Будем считать, что времени на то, чтобы отметиться на контрольном пункте и на то, чтобы пересесть с автобуса на автобус, участнику не требуется. Т.е. если, например, в момент 10 он прибывает на какой-то контрольный пункт, то дальше он может уехать любым автобусом, отправляющимся от этого контрольного пункта в момент времени 10 или позднее.
Далее вводится число \(M\) — количество контрольных пунктов в маршрутном листе участника (2≤\(M\)≤50). Далее вводятся \(M\) чисел \(P_1\), \(P_2\), …, \(P_M\) — номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте \(P_1\). Временем прохождения маршрута считается момент времени, когда участник окажется в пункте \(P_M\).
Выведите одно число — минимальное время, за которое участник может пройти маршрут. Если существующие автобусные рейсы не позволяют пройти маршрут, выведите одно число –1 (минус один).
2 2 2 1 3 1 1 2 5 4 3 1 2 1
7
3 4 2 1 30 10 1 2 50 40 2 3 45 10 3 1 55 10 3 1 2 1
65
2 2 1 2 3 1 1 2 5 4 3 1 2 1
-1