В неориентированном связном графе \(N\) вершин и \(M\) ребер, каждое из которых имеет вес, выражающийся натуральным числом (разные ребра могут иметь разные веса). В графе нет петель (т.е. ребер, ведущих из вершины в нее саму) и кратных ребер (т.е. между любыми двумя вершинами не более одного ребра).
Весом пути из одной вершины до другой называется сумма весов ребер, по которым этот путь проходит. Кратчайшим путем между двумя вершинами называется путь минимального возможного веса между этими вершинами. Считается, что длина кратчайшего пути от вершины до неё самой равна нулю.
В этом графе вычислили длины кратчайших путей между всеми парами вершин и записали их в виде таблицы. В этой таблице число на пересечении \(i\)-ой строки \(j\)-ого столбца равно длине кратчайшего пути из вершины номер \(i\) в вершину номер \(j\).
После этого исходный граф был утерян.
Напишите программу, которая по заданной таблице кратчайших расстояний восстановит какой-нибудь граф, которому эта таблица могла бы соответствовать, либо установит, что графа описанного в условии вида, которому могла бы соответствовать данная таблица, не существует.
Вводятся числа \(N\) и \(M\), а затем таблица кратчайших расстояний (\(1 ≤ N ≤ 300, 0 ≤ M ≤ 1000\), элементы таблицы кратчайших путей — целые неотрицательные числа, не превышающие \(10^6\)).
Если такой граф существует, выведите в первой строке сообщение YES, в противном случае — сообщение NO. Если граф существует, то начиная со второй строки выведите \(M\) троек чисел, описывающих ребра. Каждое ребро описывается номерами вершин, которые оно соединяет, и весом. Веса всех ребер не должны превышать \(10^6\).
4 4 0 1 2 5 1 0 3 4 2 3 0 7 5 4 7 0
YES 1 2 1 1 3 2 2 4 4 1 4 5
3 2 0 1 1 1 0 1 1 1 0
NO
Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из \(N\) подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.
Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего из выходов. Вам, как специалисту по таким задачам, поручено рассчитать необходимое время для каждого из бункеров по заданному описанию помещения Сверхсекретной организации. Для вашего же удобства бункеры занумерованы числами от 1 до \(N\).
Сначала вводятся два натуральных числа \(N\), \(K\) (\(1\) ≤ \(N\) ≤ 100000, \(1\) ≤ \(K\) ≤ \(N\)) — количество бункеров и количество выходов соответственно.
Далее через пробел записаны \(K\) различных чисел от \(1\) до \(N\), обозначающих номера бункеров, в которых расположены выходы.
Потом идёт число \(M\) (1 ≤ \(M\) ≤ 100000) — количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.
Выведите \(N\) чисел, разделенных пробелом — для каждого из бункеров минимальное время, необходимое чтобы добраться до выхода. Считайте, что время перемещения по одному туннелю равно \(1\).
3 1 2 3 1 2 3 1 2 3
1 0 1
10 2 10 8 9 6 7 7 5 5 8 8 1 1 10 10 3 3 4 4 9 9 2
1 4 1 2 1 3 2 0 3 0
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
|
|
|
Вася — начинающий программист. Последней его идеей было написать графический редактор черно-белых изображений. К сожалению, вдохновения хватило только на один инструмент — заливку.
В окне редактора картинка отображается как прямоугольная таблица M × N клеток; каждая покрашена либо в чёрный, либо в белый цвет. Две клетки назовём соседними, если у них имеется общая сторона. Областью же будем называть максимальное подмножество клеток одного цвета, такое, что из каждой можно попасть в каждую, перемещаясь только по соседним клеткам этой области.
Заливка работает следующим образом: пользователь указывает на произвольную клетку таблицы, после чего вся область, содержащая данную клетку, перекрашивается в противоположный цвет.
Теперь Вася хочет научиться стирать изображения с помощью своего редактора. Картинка считается чистой, если она либо полностью чёрная, либо полностью белая. Определите минимальное число заливок, которое потребуется для того, чтобы сделать из данного изображения чистое.
Формат входных данных
Вводятся два натуральных числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — количество строк и столбцов у таблицы, соответствующей данному изображению. В следующих N строках содержатся по M символов. В i‑й строке и j-м столбце стоит 0, если соответствующая клетка белая, и 1, если чёрная.
Формат выходных данных
Выведите одно число — минимальное количество заливок, требуемых для стирания данной картинки.
Пример
| Входные данные | Выходные данные |
| 3 5 10101 01010 10101 | 3 |
В начале XIX века еще не было самолетов, поездов и автомобилей, поэтому все междугородние зимние поездки совершались на санях. Как известно, с дорогами в России тогда было даже больше проблем, чем сейчас, а именно на N существовавших тогда городов имелась ровно N-1 дорога, каждая из которых соединяла ровно два города. К счастью, из каждого города можно было добраться в любой другой (возможно, через некоторые промежуточные города). В каждом городе имелась почтовая станция (или, как ее называют, «ям»), на которой можно было пересесть в другие сани. При этом ямщики могли долго запрягать (для каждого из городов известно время, которое ямщики в этом городе тратят на подготовку саней к поездке) и быстро ехать (также для каждого города известна скорость, с которой ездят ямщики из него). Можно считать, что количество ямщиков в каждом городе не ограничено.
Если бы олимпиада проводилась 200 лет назад, то путь участников занимал бы гораздо большее время, чем сейчас. Допустим, из каждого города в Москву выезжает участник олимпиады и хочет добраться до Москвы за наименьшее время (не обязательно по кратчайшему пути: он может заезжать в любые города, через один и тот же город можно проезжать несколько раз). Сначала он едет на ямщике своего города. Приехав в любой город, он может либо сразу ехать дальше, либо пересесть. В первом случае он едет с той же скоростью, с какой ехал раньше. Решив сменить ямщика, он сначала ждет, пока ямщик подготовит сани, и только потом едет с ним (естественно, с той скоростью, с которой ездит этот ямщик). В пути можно делать сколько угодно пересадок.
Жюри стало интересно, какое время необходимо, чтобы все участники олимпиады доехали из своего города в Москву 200 лет назад. Все участники выезжают из своих городов одновременно.
В первой строке входного файла дано натуральное число N, не превышающее 2000 — количество городов, соединенных дорогами. Город с номером 1 является столицей.
Следующие N строк содержат по два целых числа: Ti и Vi — время подготовки саней в городе i, выраженное в часах, и скорость, с которой ездят ямщики из города i, в километрах в час (0 ≤ Ti ≤ 100, 1 ≤ Vi ≤ 100).
Следующие N–1 строк содержат описания дорог того времени. Каждое описание состоит из трех чисел Aj, Bj и Sj, где Aj и Bj — номера соединенных городов, а Sj — расстояние между ними в километрах (1 ≤ Aj ≤ N, 1 ≤ Bj ≤ N, Aj ≠ Bj, 1 ≤ Sj ≤ 10000). Все дороги двусторонние, то есть если из A можно проехать в B, то из B можно проехать в A. Гарантируется, что из всех городов можно добраться в столицу.
Сначала выведите одно вещественное число — время в часах, в которое в Москву приедет последний участник.
Далее выведите путь участника, который приедет самым последним (если таких участников несколько, выведите путь любого из них). Выведите город, из которого этот участник выехал первоначально, и перечислите в порядке посещения те города, в которых он делал пересадки. Последовательность должна заканчиваться столицей.
При проверке ответ будет засчитан, если из трех величин «время путешествия по выведенному пути», «выведенное время» и «правильный ответ» каждые две отличаются менее чем на 0.0001.
Комментарий к примеру тестов
1. Участник из города 1 уже находится на своем месте и тратит на дорогу 0 часов. Участник из города 2 ждет 10 часов ямщика в своем городе, а затем проезжает 300 км от города 2 до города 1 за 10 часов, т.е. тратит на дорогу 20 часов. Участник из города номер 3 ждет ямщика 5 часов, а затем доезжает до города 1 за 10 часов, т.е. тратит на дорогу 15 часов. Участник из города 4 может доехать до города 1 с ямщиком из города 4 за 1 + 40 = 41 час или доехать до города номер 2 за 1 + 10 = 11 часов, прождать там 10 и доехать до столицы за 10 часов. Таким образом, он может добраться до города 1 минимум за 31 час. Это и есть самое большое время и ответ к задаче.
2. Участнику из города 2 выгоднее добраться сначала до третьего города, где ездят быстрее, а потом поехать в столицу, не делая пересадки в своём городе.
4 1 1 10 30 5 40 1 10 1 2 300 1 3 400 2 4 100
31.0000000000 4 2 1
3 1 1 0 10 0 55 1 2 100 2 3 10
3.0000000000 2 3 1
В столице одной небольшой страны очень сложная ситуация. Многокилометровые пробки буквально парализовали движение в городе, и власти на многих улицах ввели одностороннее движение, не анализируя, можно ли будет теперь проехать из любого места в городе в любое другое, не нарушая правила. Транспортная система столицы представляет собой N площадей, соединенных M полосами для движения, в том числе круговыми полосами, проходящими по площади. Каждая полоса предназначена для движения только в одну определенную сторону. При этом на магистралях есть полосы, направленные как в одну, так и в другую сторону. По круговой полосе можно двигаться только внутри площади и только против часовой стрелки.
Власти города на каждой полосе разместили видеокамеру, поэтому если Иннокентий едет по встречной полосе (при ее наличии) или, в случае одностороннего движения, в сторону противоположную предписанной знаками, то после поездки против правил по каждой из полос ему придется заплатить штраф в размере одной тысячи тугриков этой страны.
Иннокентий, который торопится купить кафельную плитку со скидкой, решился доехать до магазина в любом случае, даже если для этого придется нарушать правила. Но он хочет выбрать такой маршрут движения, суммарный штраф на котором минимален.
Иннокентий еще не решил, откуда именно и в какой магазин он собирается ехать, поэтому ему необходимо ответить на несколько вопросов вида «Какой минимальный штраф надо заплатить, чтобы добраться из пункта A в пункт B?». Отвечая на потребности жителей столицы, известная поисковая система Индекс разрабатывает соответствующий сервис.
Так как многие из вас рано или поздно будут проходить собеседование на работу в эту фирму, продемонстрируйте, что вы тоже умеете решать эту задачу.
В первой строке входных данных содержатся два числа N и M — количество площадей и полос движения в городе соответственно (1 ≤ N ≤ 5000, 1 ≤ M ≤ 10 000). Далее содержатся описания полос, по которым движение разрешено. Каждая полоса описывается номерами двух площадей, которые она соединяет. Движение разрешено в направлении от первой из указанных площадей ко второй.
В следующей строке содержится одно число K — количество вопросов у Иннокентия (1 ≤ K ≤ 10 000, N·K ≤ 2·107). В следующих строках описываются вопросы, каждый вопрос описывается номерами двух площадей, между которыми требуется найти самый дешевый путь. Путь необходимо проложить от первой из указанных площадей ко второй.
Для каждого вопроса выведите одно число — искомый минимальный размер штрафа в тысячах тугриков. В случае, если пути между выбранной парой площадей не существует, выведите - 1.
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
5 5 2 1 2 4 3 2 4 3 5 4 3 5 1 1 5 2 3
0 2 0