Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Одуванчики#26996

У Ани есть поле размером N×M клеток. На этом поле Аня разводит одуванчики. Аня заметила, что если в некоторой клетке поля растёт одуванчик, то на следующий день в четырёх клетках рядом с ним (севернее, восточнее, южнее и западнее) вырастает по одуванчику. Однако за пределами поля одуванчики не вырастают.

Сейчас на поле растёт несколько одуванчиков (не меньше одного). Определите, через сколько дней всё поле будет в одуванчиках. Известно, что Аня хорошо заботится о выросших одуванчиках, поэтому ни один из них не погибнет.

Формат входных данных

На первой строке находятся числа N и M (1<=N, M <= 100) размеры поля. Далее идут N строк, каждая из которых по M элементов. Эти строки обозначают поле. Символ «.» в строке означает, что данная клетка поля пуста, а символ «*» что в клетке находится одуванчик. Других символов в строках быть не может.

Формат выходных данных

Выведите единственное число - количество дней, которое должно пройти, чтобы всё поле оказалось засеянным одуванчиками.

Частичные решения, работающие при случаях, когда N = 1 или M = 1, получат не менее 30 баллов.

Ввод	Вывод
3 3 ... .*. ...	2
4 3 ... ... ... *..	5

Обход в ширину

✓ 13✗ 54800средняяВойти и решать

Эвакуация#24913

Через T минут армия читаури под предводительством Локи атакует Землю. Мстители никак не успевают помешать открытию портала в Нью-Йорке, поэтому Капитан Америка принял решение эвакуировать из города всех его жителей. Ему необходимо выяснить, успеют ли жители города эвакуироваться до начала вторжения.

Окрестности Нью-Йорка можно представить как набор небольших городов, связанных между собой дорогами с односторонним движением. Каждая дорога характеризуется своей длиной и пропускной способностью. Длина дороги l означает, что въехав на нее в момент времени t, автомобиль окажется в конце этой дороги через l минут, в момент времени t + l. Пропускная способность дороги s означает, что каждую минуту на эту дорогу могут въехать не больше, чем s автомобилей. Приехав в какой-нибудь город, любой автомобиль может сразу продолжить путь, въехав на какую-то дорогу, выходящую из этого города, а может остановиться в этом городе на любое количество минут, и только потом уехать из него.

Капитан Америка уже решил, в каком именно городе должны оказаться жители Нью-Йорка после эвакуации. Также ему известно, сколько автомобилей необходимо для эвакуации всего города. Теперь ему необходимо выяснить успеют ли все жители эвакуироваться до прибытия захватчиков и, если да, какое минимальное количество времени у них на это уйдет, а если нет какому минимальному числу автомобилей с горожанами не удастся доехать до безопасного города.

Формат входного файла

Первая строка входного файла содержит четыре целых числа n, m, K и T (1 ≤ n x T ≤ 10 000, 1 ≤ m, K ≤ 10 000) количество городов в окрестностях Нью-Йорка, количество дорог между ними, количество автомобилей, которым необходимо попасть из Нью-Йорка в безопасный город и время до вторжения захватчиков соответственно. Следующие m строк содержат описания дорог между городами.

Каждая дорога описывается четырьмя целыми числами u, v, l и s (1 ≤ u, v ≤ n, u != v, 1 ≤ s ≤ 3 000, 1 ≤ l ≤ 200) город, из которого выходит эта дорога, город, в который она ведет, ее длина и пропускная способность соответственно.

Между двумя городами может существовать только одна дорога, ведущая в каком-то направлении. Нью-Йорком считается город с номером 1, а безопасным городом город с номером n. в момент времени 0 все автомобили находятся в Нью-Йорке.

Формат выходного файла

Если все жители Нью-Йорка успеют добраться до безопасного города не более, чем за T минут, выведите в выходной файл минимальное количество минут, которое им на это понадобится. В противном случае выведите минимальное количество автомобилей, которым не удастся попасть в безопасное место за T минут. Да, не нужно выводить, какой из этих случаев имеет место :-).

Ввод	Вывод
5 5 10 10 1 2 2 2 2 3 1 1 2 4 1 1 4 5 2 4 3 5 2 4	9

Обход в глубину

✓ 0✗ 61 300средняяВойти и решать

Путь в никуда#24761

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

Бинарный поиск Деревья Префиксные суммы(минимумы, ...)Разреженные таблицы (sparse table)Структуры данных

✓ 17✗ 49800средняяВойти и решать

Orders#24733

Блейз отправляет приказы на перемещение своим войскам, собранным из жителей одной из теней. К сожалению, они не понимают амберский язык, поэтому Блейзу приходится отправлять им сообщения на их родном языке.
В этом и заключается проблема: Амберийский принц плохо знает орфографию этого языка, поэтому иногда он делает ошибки в словах, но не более одной ошибки в слове.
В языке очень много слов, поэтому если в слове изменится хотя бы одна буква, то его смысл может кардинально измениться. Если армия не правильно поймет приказ, то вся военная кампания может провалиться. Поэтому Блейзу очень важно проверять правильность в написании слов. Он решил попросить вас помочь ему.
Вы должны создать программу, которая будет выводить в лексикографическом порядке все возможные слова, которые Блейз мог пытаться написать с учетом того, что он мог ошибиться 1 раз.

Входные данные
В первой строке на вход подается числа n и m - количество приказов, которые отдал Блейз, и количество команд, которые понимают его войска соответственно. (1 <= n, m <= 5000)
В следующей строке на вход подаются m слов - команды, которые понимают войска Блейза.
В следующих n строках на вход подаются слова - приказы, которые отдает Блейз.
Все строки длиной не превышают 100.

Выходные данные

Выведите n строк: в строке номер i содержится ответ на задачу для приказа Блейза номер i. Строки, являющиеся ответом на этот запрос, выводятся через пробел в одну строку.

Пример
Ввод

5 5
is in if on of
it
in
of
ij
op

Вывод
if in is
if in is on
if of on
if in is
of on

(с) Евгений Григорьев

Бор Обход в глубину Перебор

✓ 7✗ 241 100средняяВойти и решать

ЭПИЗОД X ФИРИОН НАНОСИТ ОТВЕТНЫЙ УДАР#24727

ЭПИЗОД X: ФИРИОН НАНОСИТ ОТВЕТНЫЙ УДАР
Берляндия наконец-то окрепла после крупного поражения в войне против Стерляндии, и император Берляндии Фирион готовит атаку на противника.
Стерляндия представляет собой определенное количество городов, соединенных двусторонними дорогами. От любого города Стерляндии можно добраться до любого другого. Никакая дорога не соединяет город с самим собой.
Планируется следующее:
Выбирается город, на который будет производиться атака. Город уничтожают, а дороги, исходящие из него, баррикадируются. При этом Стерляндия должна потерять свою целостность. Далее одна из образованных областей подвергается атаке. При этом эта область должна составлять не менее 1/8 и не более 1/4 от оставшейся площади страны ( площадь измеряется в количестве городов в данной области). Если при разрушении города Стерляндия сохраняет целостность, или подходящих областей не образуется, то данный город не подходит для атаки.
Фирион хочет знать сколько городов удовлетворяют выше описанным условиям, а также номера этих городов в порядке возрастания.
Входные данные
В первой строке даны два числа: n – кол-во городов в Стерляндии ( 2 <= n <= 10^3), m – количество дорог в Стерляндии ( 1 <= m <= 10^4).
Далее идут m строк, в которых задается описание дорог, а именно: в каждой строке заданы два числа: X и Y. Это означает, что город X и город Y соединены дорогой.
Выходные данные
В первой строке выведите число s – кол-во городов, подходящих для атаки. Во второй строке выведите s чисел - номера таких городов в порядке возрастания.
Пример

5 5
1 2
1 3
2 3
3 4
4 5

1
4

графы Точки сочленения

✓ 8✗ 391 000средняяВойти и решать

ГОЛБЕЗ В БЕРЛЯНДИИ#24726

ГОЛБЕЗ В БЕРЛЯНДИИ
Турист Голбез очень любит путешествовать. На этот раз он решил посетить Берляндию.
Берляндия представляет собой определенное количество городов, соединенных двусторонними дорогами. От любого города Берляндии можно добраться до любого другого. Никакая дорога не соединяет город с самим собой.
Будем называть дорогу дорогой федерального значения, если существует любая пара городов v и u ( v != u), такая, что любой путь от v до u лежит через эту дорогу. Будем называть город городом федерального значения, если все дороги, исходящие из этого города являются дорогами федерального значения.
Голбез решил посетить все города федерального значения Берляндии. Помогите ему определить какие именно города ему необходимо посетить.
Входные данные
В первой строке даны два числа: n – кол-во городов в Берляндии ( 2 <= n <= 10^5), m – количество дорог в Берляндии ( 1 <= m <= 10^6).
Далее идут m строк, в которых задается описание дорог, а именно: в каждой строке заданы два числа: X и Y. Это означает, что город X и город Y соединены дорогой.
Выходные данные
В первой строке выведите число s – кол-во городов федерального значения. Во второй строке выведите s чисел - номера городов федерального значения в порядке возрастания.
Пример

5 5
1 2
1 3
2 3
3 4
4 5

2
4 5

Мосты

✓ 22✗ 24800средняяВойти и решать

Компоненты связности#22021

В неориентированном графе посчитать количество компонент связности. В графе могут быть петли и кратные ребра.

Входные данные: В первой строке записаны сначала два числа N и M, задающие соответственно количество вершин и количество ребер (1<=N<=100, 0<=M<=10000), а затем перечисляются ребра. Каждое ребро задается двумя номерами вершин, которые оно соединяет.

Выходные данные: Выведите одно число - количество компонент связности

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 1 2 1 3 2 3	1
2	5 3 1 1 1 2 2 1	4
3	5 0	5

Обход в глубину

✓ 1 109✗ 1 373300лёгкаяВойти и решать

Путь#22020

В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Формат входных данных
В первой строке записано число N - количество вершин в графе (1 <= N <= 100). В следующих строках задана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.

Формат выходных данных
Выведите сначала L - длину пути (количество ребер, которые нужно пройти). Затем выведите L+1 число - вершины в порядке следования вдоль этого пути. Если пути не существует, выведите одно число -1.

Примеры

№	Входные данные	Выходные данные
1	5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5	3 3 2 1 5

Обход в ширину

✓ 723✗ 1 979600лёгкаяВойти и решать

Цветной дождь#22019

В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых - синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся.
Посчитать количество таких "плохих" мостов.

Формат входных данных
В первой строке записано N (\(0<N<=100\)) - число холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). В последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый.

Формат выходных данных
Вывести количество "плохих" мостов.

Способы задания графа

✓ 1 219✗ 782400лёгкаяВойти и решать

Светофорчики-1#22018

В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

Формат входных данных
В первой строке записано два числа N и M (\(0<N<=100\), \(0<=M<=N*(N-1)/2\) ). В следующих M строках записаны по два числа i и j (\(1<=i,j<=N\)), которые означают, что перекрестки i и j соединены тоннелем.

Формат выходных данных
Вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

Примечание
Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

Способы задания графа

✓ 1 334✗ 1 004400лёгкаяВойти и решать

Города и дороги#22017

В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.

Формат входных данных
В первой строке задается число N (\(0<=N<=100\)). В следующих N строках записано по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.

Формат выходных данных
Вывести одно число - количество дорог на планете "Neptune".

Примечание

Все дороги двусторонние, то есть если есть дорога из города i в город j, то есть и дорога из города j в город i, и это та же самая дорога.

Способы задания графа

✓ 1 607✗ 1 061300лёгкаяВойти и решать

Выборы#21952

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

Казалось бы, чтобы выиграть, необходимо убедить проголосовать за нашего кандидата более половины пришедших на выборы. Оказывается, что иногда нужно гораздо меньше! Для того чтобы понять, как это возможно, рассмотрим подробнее процедуру голосования.

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

Формат входных данных

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

На рисунке 1 черным цветом отмечены те регионы, в которых победил Дядя Сэм. На нижнем уровне черными изображены вершины, соответствущие подкупленным конкретным жителям.

Алгоритмы на графах Динамическое программирование Динамическое программирование: один параметр Простые числа и разложение на множители

✓ 2✗ 771 200средняяВойти и решать

Магические порталы#21903

В некотором королевстве есть n городов, соединенных магическими порталами. Каждая пара различных городов соединена ровно одним магическим порталом, позволяющим мгновенно перемещаться из одного города в другой.

Из-за свойств магии, определяющей работу порталов, каждый портал можно использовать только в одну сторону. Для каждой пары городов A и B известно, можно ли воспользоваться порталом для перемещения напрямую из A в B или из B в A.

Из-за особенностей магических порталов иногда при перемещении жителей королевства из одного города в другой приходится использовать несколько порталов. Также могут существовать такие пары городов, что из одного города в другой нельзя добраться, используя только магические порталы.

Жители королевства называют город совершенным, если из него можно добраться до любого другого города в королевстве, используя только магические порталы. Пусть изначально количество совершенных городов в королевстве равно k.

Недавно король принял решение выбрать пару городов и изменить разрешенное направление перемещения по порталу, соединяющему их, на противоположное. Для выбора лучшего варианта король хочет понять, какое количество совершенных городов может оказаться в королевстве после перенастройки ровно одного портала.

Для получения этой информации король планирует запросить в министерстве транспорта соответствующий отчет. Король может запросить либо частичный, либо полный отчет. Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1, для полного отчета L = 1.

Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B, для которых выполняются следующие условия:
- исходно магический портал позволяет перемещаться напрямую из города A в город B;
- если изменить направление перемещения этого магического портала на противоположное, чтобы он позволял напрямую перемещаться из города B в город A, то количество совершенных городов в королевстве станет равным m.

Таким образом, частичный отчет содержит информацию только о тех способах перенастройки одного портала, которые строго увеличивают количество совершенных городов в королевстве. Полный отчет содержит информацию обо всех способах перенастройки одного портала.

Требуется написать программу, которая по информации о разрешенных направлениях перемещения с использованием магических порталов, и информации о том, требуется предоставить частичный или полный отчет, формирует соответствующий отчет и выводит его в описанном ниже формате.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — количество городов в королевстве (2 ≤ n ≤ 2000) и p, равное либо 0, если требуется вывести частичный отчет, либо 1, если требуется вывести полный отчет. Последующие n строк содержат по n символов, каждый из которых может быть «+», «–» или «.», и i-я из этих строк описывает магические порталы, соединяющие i-й город с другими городами.
В i-й строке j-й символ равен «+», если магический портал позволяет напрямую перемещаться из i-го города в j-й, равен «–», если магический портал позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.
Формат выходного файла
Первая строка выходного файла должна содержать одно целое число k — количество совершенных городов в королевстве.
Если требуется частичный отчет (p = 0), то вторая строка выходного файла должна содержать (n – k) целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным (k + i). Если при этом k = n, то вторая строка может отсутствовать, либо быть пустой.
Если требуется полный отчет (p = 1), то вторая строка должна содержать n целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным i.

Пример:

Ввод	Вывод
5 0 .-+++ +.+++ --.+- ---.+ --+-.	1 0 0 0 3
5 1 .-+++ +.+++ --.+- ---.+ --+-.	1 7 0 0 0 3

Пояснение к примерам

В приведенных примерах изначально совершенным является только город 2.
Изменив направление порталов, соединяющих пары городов (2, 3), (2, 4) или (2, 5), можно сделать все города совершенными. Изменение направление любого другого портала делает совершенным один город.

Алгоритмы на графах Задача на реализацию Циклы

✓ 1✗ 101 300средняяВойти и решать

Друзья#21825

В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.

Входные данные

В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.

Выходные данные

В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

Ввод:

3 1

0 1 0

1 0 1

0 1 0

Вывод
2

графы Поиск компонент связности

✓ 0✗ 51 200средняяВойти и решать

Запросы по Флойду#21777

Дан неориентированный взвешенный граф с отрицательными весами, необходимо выдавать информацию о кратчайшем пути между 2 вершинами.

Входные данные
В первой строчке дано целое число n - количество вершин в графе. Дальше на вход подается матрица смежности, в которой -1 означает отсутствие ребра между вершинами. После матрицы идет число k - количество запросов, в следующих k строках содержится по 2 числа, a и b - вершины в запросе.

Выходные данные
Выведите k чисел - расстояние между парой чисел из запроса в порядке их ввода, если нельзя добраться из вершины a в вершину b, следует вывести Imp. Каждое число выводится в отдельной строке.

Примеры

№	Входные данные	Выходные данные
1	3 0 3 -1 3 0 4 -1 4 0 3 1 3 3 2 1 2	7 4 3

Алгоритм Флойда

✓ 277✗ 465500лёгкаяВойти и решать

Дейкстра: Расстояние до всех вершин#21776

Дан неориентированный взвешенный граф, необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм Дейкстры.

Входные данные:

В 1 строке даны 2 целых числа n и m (n>=1, m >= 0), число вершин и ребер в графе соответсвенно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра .

Выходные данные:

Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.

Ввод	Вывод
5 5 1 2 3 2 3 1 3 4 3 1 4 1 4 2 1	2 3 1 Impossible

P.S. Внимательно проверяйте ограничения

Алгоритм Дейкстры

✓ 18✗ 42700средняяВойти и решать

Беллман#21775

Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).

Дана стартовая и конечная вершина, определить минимальное расстояние между ними.

Входные данные:

Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.

В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.

Выходные данные:

Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.

Примеры

№	Входные данные	Выходные данные
1	4 2 1 4 1 2 100500 2 3 100500	Inf

Алгоритм Форда-Беллмана

✓ 89✗ 137400лёгкаяВойти и решать

1 - k BFS#21770

Дан ориентированный взвешенный граф. Необходимо найти расстояние от вершины 1 до всех остальных, используя алгоритм 1 - k BFS.

Входные данные
В первой строке даны 2 целых числа n и m, число вершин и ребер в графе соответственно. В следующих m строках дается по 3 числа a и b - вершины которые соединяет ребро и c - вес этого ребра (a, b, c >= 0).

Выходные данные
Необходимо вывести n-1 число через пробел - расстояния от вершины 1 до всех остальных, если нет возможного пути из 1 в i вершину, то необходимо вывести Impossible.

Примеры

№	Входные данные	Выходные данные
1	9 9 1 2 1 2 4 2 4 6 1 4 3 1 3 5 2 5 6 1 8 9 100 9 7 100 7 8 100	1 4 3 6 4 Impossible Impossible Impossible

0-1 BFS

✓ 68✗ 124800средняяВойти и решать

Перекрестные ребра#21710

Дан связный ориентированный невзвешенный граф. Требуется вывести номера вершин из которых исходят все его перекрестные ребра (нумерация с 1).

Входные данные:

Целое число n и m - число вершин и ребер в графе.

Следующие m строк содержат 2 числа a и b, показывающие, что из вершины a есть ребро в вершину b.

Выходные данные:

В первой строке должно находиться число n - количество перекрестных ребер, в следующей строке должны быть перечисленны вершины в порядке возрастания без повторений. Если таковых нет, тогда следует вывести -1.

Обход в глубину поиск в глубину и подобное

✓ 17✗ 8500лёгкаяВойти и решать

Точки сочленения#21708

Вам задан неориентированный связный граф с N вершинами и М ребрами (1 ? N ? 20000, 1 ? М ? 200 000). В графе отсутствуют петли и кратные ребра.

Найдите все точки сочленения в заданном графе.

Формат входного файла:

Граф задан во входном файле следующим образом: первая строка содержит числа N и М. Каждая из следующих М строк содержит описание ребра - два целых числа из диапазона от 1 до N - номера концов ребра.

Формат выходного файла:

На первой строке выведите число С - количество точек сочленения в заданном графе. На следующей строке выведите С целых чисел - номера вершин, которые являются точками сочленения, в возрастающем порядке.

Точки сочленения

✓ 20✗ 43900средняяВойти и решать