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

Vacation Planning (gold)#89866

Air Bovinia выполняет полёты, соединяющие N (1 <= N <= 20,000) ферм, в которых живут коровы. K (1 <= K <= 200, K <= N) из этих ферм назначены хабами.
Сейчас Air Bovinia предлагает M (1 <= M <= 20,000) однонаправленных полётов, где полёт i производится из фермы u_i в ферму v_i и стоит d_i (1 <= d_i <=10,000) долларов. Для каждого из этих полётов или u_i или v_i является терминалом. Существует не более одного полёта между любыми двумя фермами в любом заданном направлении, и не существует полёта, который начинается и заканчивается в одной и той же ферме.
Беси руководитель службы занимающейся билетами. Получено Q (1 <= Q <= 50,000) однонаправленных запросов на путешествие, где i-ый запрос – перелёт из фермы a_i на ферму b_i.
Напишите программу, которая определит можно ли выписывать билет и, если да, то какова будет его минимальная стоимость.
Чтобы сократить размер вывода Вы должны вывести только общее количество билетов, которые можно выписать и суммарную их минимальную стоимость. Заметим, что это число может не поместиться в 32-битное целое.
PROBLEM NAME: vacationgold
Формат входных данных
* Строка 1: Целые числа N, M, K, Q.
* Строки 2..M + 1: Строка i+1 содержит u_i, v_i, и d_i. (1 <= u_i, v_i <= N, u_i != v_i)
* Строки M + 2..M + K + 1: Каждая из этих строк содержит ID одного хаба (в интервале 1..N).
* Строки M + K + 2..M + K + Q + 1: Два числа на строке, указывающие запрос на билет из фермы a_i на ферму b_i (1 <= a_i, b_i <=N, a_i != b_i)
Формат выходных данных
* Строка 1: Количество билетов, которые могут быть выписаны
* Строка 2: Минимальная общая стоимость всех выписанных билетов
Примечание
Для первого полёта есть только один маршрут 1->2->3 с ценой 20. Нет полётов из фермы 3, поэтому бедные коровы останутся там.

кратчайшие пути

—Войти и решать

Milk Routing#89813

На ферме Джона имеется сеть из M труб (1 <= M <= 500) для передачи молока от фермы к молокохранилищу. ФД хочет удалить и заменить некоторые из труб, но оставить ровно один путь, так чтобы он смог по прежнему передавать молоко из амбара в хранилище.
Сеть труб описывается N точками соединения (1 <= N <= 500), каждая из которых может служить конечной точкой множества труб. Точка соединения номер 1 - это амбар, а точка соединения номер N - молокохранилище. Каждая из M двунаправленных труб соединяет пару точек соединения и имеет время задержки - (количество времени, которое требуется чтобы молоко достигло одного конца из другого) пропускную способность - количество молока в единицу времени, которое может быть передано по этой трубе. Пары точек соединения могут соединяться более чем одной трубой.
Для пути от амбара к хранилищу время задержки - это сумма всех времен задержки всех труб в этом пути. А пропускная способность пути - минимум из пропускных способностей всех труб этого пути. Если ФД хочет передать X единиц молока через путь с временем задержки L и пропускной способностью C, то требуемое время равно L + X/C.
По заданной структуре сети труб ФД помогите ему выделить один путь от амбара к хранилищу, который позволит ему передать X единиц молока за минимальное количество времени.
PROBLEM NAME: mroute
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N M X (1 <= X <= 1,000,000).
* Строки 2..1+M: Каждая строка описывает трубу 4-мя целыми числами: I J L C. I и J (1 <= I,J <= N) точки соединения обоих концов трубы L и C (1 <= L,C <= 1,000,000) задают время задержки и пропускную способность трубы.
Формат выходных данных
* Строка 1: Минимальное количество времени, которое потребуется чтобы передать молоко по единственному пути, округленное вниз до ближашего целого.

Примечание
Путь 1->3 занимает 14 + 15/1 = 29 единиц времени. Путь 1->2->3 занимает 20 + 15/2 = 27.5 единиц времени, и поэтому оптимальный.

кратчайшие пути

—Войти и решать

Roadblock#89794

Каждое утро Фермер Джон идет от дома к амбару. Ферма представляет собой множество из N полей (1 <= N <= 100) (дом на поле 1, амбар на поле N), соединенных M (1 <= M <= 10,000) двунаправленными дорогами, с каждой из которых ассоциирована длина.
Никакие два поля не соединены более чем одной дорогой, и существует маршрут дорог от любого поля к любому. Когда ФД идет от одного поля к другому, он всегда выбирает маршрут, состоящий из последовательности дорог, которые дают минимальную суммарную длину.
Коровы решили сделать ФД маленькую неприятность, выложив сено на одной из M дорог, тем самым удваивая ее длину.
Коровы хотят выбрать такую дорожку, чтобы максимально увеличить расстояние, которое ФД пройдет от дома до амбара. Помогите коровам определить, насколько они удлинят маршрут ФД.
PROBLEM NAME: rblock
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N (1 <= N <= 100) и M (1 <= M <= 10,000).
* Строки 2..1+M: Строка j+1 описывает j-ую двунаправленную дорожку тремя разделенными пробелами целыми числами A_j B_j L_j, где A_j и B_j это числа от 1 до N, указывающие поля, соединенные этой Дорогой, а L_j - длина этой дороги (в диапазоне 1...1,000,000).
Формат выходных данных
* Строка 1: Максимально возможное увеличение общей длины кратчайшего маршрута, которого можно добиться удвоением длины одной дороги.
Примечание
Если коровы удвоят длину дороги от поля 3 к полю 4 (от 3 до 6), тогда кратчайшим маршрутом станет путь 1-3-5, с общей длиной 1+7= 8. Что на 2 больше, чем исходный кратчайший маршрут.

графы кратчайшие пути реализация

—Войти и решать

Кейс на рейс#60841

Авиакомпания <<Флагманский Флот Татарстана>> предлагает в своих самолётах новый вид бизнес-класса. Салон самолёта состоит из \(n\) мест, расположенных в один ряд вдоль прохода. Введём координатную прямую вдоль салона так, что расстояние между креслами будет равно \(1\), и места будут иметь координаты от \(1\) до \(n\).

Во время полёта стюарду нужно пройти по самолету и раздать всем пассажирам напитки. Напитки бывают \(k\) разных видов, пронумерованных числами от \(1\) до \(k\). Каждый пассажир получает одну порцию одного напитка, пассажир заказывает предпочитаемый вид напитков при бронировании билета, поэтому все предпочтения пассажиров известны заранее.

Напитки разлиты по бутылкам, каждая бутылка вмещает \(p\) порций одного напитка. В тележку для напитков можно загрузить не более \(m\) бутылок с любыми видами напитков, гарантируется, что \(m\ge k\).

Пассажиры обслуживаются в порядке возрастания номеров их мест. Первоначально тележка находится в начале салона в точке \(0\), и её можно заполнить любыми видами напитков перед обслуживанием. После завершения обслуживания тележка должна приехать в точку \(n+1\). При этом в точках \(0\) и \(n+1\) могут находиться кладовые: или одна кладовая в одном из концов салона или две кладовые в двух концах, в которых имеется достаточный запас напитков каждого вида. В этих кладовых можно выгрузить из тележки пустые бутылки и погрузить полные бутылки.

По ходу обслуживания напитки будут расходоваться, поэтому время от времени возникает необходимость пополнить запас напитков на тележке в одной из кладовых. Если в текущий момент тележка находится напротив кресла номер \(i\), то для того, чтобы доехать до кладовой в точке \(0\) необходимо проехать расстояние \(i\), а для того, чтобы доехать до кладовой в точке \(n + 1\) необходимо проехать расстояние \(n+1-i\). В кладовых можно выгрузить пустые бутылки из тележки и загрузить на свободные места бутылки с напитками любых видов. Выгружаемые бутылки должны быть пустыми, нельзя выгружать бутылки, в которых остались напитки, или выливать напитки. Нельзя переливать остатки напитков между разными бутылками. Можно загружать на тележку более одной бутылки одного вида. После этого тележка должна проехать расстояние от кладовой до кресла первого необслуженного пассажира, чтобы продолжить обслуживание.

Определите, какое минимальное расстояние должна проехать тележка, чтобы переместиться из точки \(0\) в точку \(n+1\) и обслужить всех пассажиров.

Формат входных данных
Первая строка входных данных содержит четыре целых числа \(n\), \(m\), \(k\), \(p\) (\(3 \leq n \leq 10^6\), \(1 \leq p \leq 10^6\), \(1 \leq k \leq m \leq 10^6\)) — количество мест в салоне, вместимость тележки, количество типов напитков и вместимость каждой бутылки соответственно.

В следующей строке содержится целое число \(c\) (\(1 \leq c \leq 3\)) — параметр, описывающий наличие кладовых в салоне. Если \(c=1\), то кладовая находится только в точке \(n+1\). Если \(c=2\), то кладовая находится только в точке \(0\). Если \(c=3\), то кладовые находятся в обоих концах салона.

В следующей строке содержатся \(n\) целых чисел \(a_i\) (\(1 \leq a_i \leq k\)) — типы напитков, которые заказали пассажиры.

Формат выходных данных
Программа должна вывести одно целое число — минимальное расстояние, которое должна проехать тележка.

Пояснения к примерам
В первом примере в тележку вмещается \(m=2\) бутылки по \(p=1\) порции в каждой. Кладовая находится в конце салона. Первоначально тележку нужно загрузить бутылками с напитками вида \(1\) и \(2\), которые будут налиты пассажирам на местах \(1\) и \(2\), тележка проедет расстояние \(2\) от точки \(0\) до точки \(2\). После этого тележке нужно будет проехать до кладовой в конце салона (расстояние \(4\)), загрузить тележку бутылками вида \(1\) и \(2\) и вернуться к креслу номер \(3\) (тележка проедет расстояние \(3\)). Пассажирам на местах \(3\) и \(4\) выдаются напитки вида \(1\) и \(2\) (тележка проезжает расстояние \(1\) от места \(3\) до места \(4\)). После этого тележке понадобится ещё раз съездить в кладовую (от кресла \(4\) до кладовой расстояние \(2\)), вернуться из кладовой до кресла \(5\) (расстояние \(1\)), и проехать ещё \(1\) до конца салона. Общее расстояние равно \(2+4+3+1+2+1+1=14\).

Во втором примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой. Кладовая находится в начале салона. Необходимо загрузить тележку тремя бутылками вида \(1\), обслужить пассажиров на местах с номерами от \(1\) до \(4\). После этого опустошатся две бутылки вида \(1\), нужно будет сразу съездить в кладовую, чтобы загрузить две бутылки вида \(2\), затем обслужить пассажиров на местах с номерами от \(5\) до \(8\).

В третьем примере в тележку вмещаются \(m=3\) бутылки по \(p=2\) порции в каждой, кладовые находятся в обоих концах салона. Для обслуживания пассажиров нужны две бутылки вида \(2\) и по одной бутылке видов \(1\) и \(3\), поэтому понадобится один раз съездить в кладовую для того, чтобы заменить пустую бутылку вида \(2\) на полную. Это лучше сделать после обслуживания пассажира на месте \(3\), тележка должна съездить в кладовую в начале салона.

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

В пятом примере понадобится два пополнения тележки, один раз тележке придётся вернуться в кладовую в начало салона после обслуживания пассажира \(3\), второй раз — в конец салона после обслуживания пассажира \(6\).

кратчайшие пути реализация

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

Злой лифт#55504

Дизайн-студия Артемия Индюкова получила заказ на разработку очень пафосного лифта для нового небоскреба. За работу взялся сам Артемий, отличающейся, кстати, редкой неадекватностью. У него есть идея-фикс: для управления лифтом достаточно четырех кнопок. Кнопки должны быть следующие:

- Поднятся на A этажей вверх
- Поднятся на B этажей вверх
- Поднятся на C этажей вверх
- Спустится на первый этаж

Изначально лифт находится на первом этаже. Пассажир лифта использует первые три кнопки чтобы попасть на тот этаж, на который он хочет. Если пассажир пытается подняться вверх на A, B или C этажей, а такого этажа в здании не существует (т.е. пассажир хочет подняться выше N-го, последнего этажа), то лифт никуда не едет.
Заказчики проекта оказались с юмором и вместе с отказом от футуристичного дизайна решили оценить адекватность Артемия по шкале от 1 до N. Оценка адеватности равна количеству этажей, на которые можно попасть с первого с помощью такого лифта. Помогите им в этом.

Входные данные
Первая строка содержит число N – высоту небоскреба (1 <= N <= 10¹⁸).

Вторая строка содержит три числа A, B и C, задающие параметры кнопок (1 <= A, B, C <= 100 000).

Выходные данные
Выведите единственное число — оценку адекватности Артемия Индюкова.

кратчайшие пути реализация теория чисел

✓ 1✗ 0—Войти и решать

Модульный граф#50365

Дан связный неориентированный граф из \(n\) вершин. Изначально в \(i\)-й вершине (\(1 \leq i \leq n\)) записано целое положительное число \(a_i\). Боб хочет за минимальное время попасть из вершины с номером \(1\) в вершину с номером \(n\). Время, которое требуется, чтобы пройти по ребру, соединяющему вершины \(u\) и \(v\), составляет \(|a_u - a_v|\).

Перед тем, как начать обход, Боб может поменять значение \(a_i\) в не более чем \(k\) вершинах. За какое минимальное время можно попасть из \(1\) в \(n\), поменяв значения оптимальным образом?

Формат входных данных
В первой строке входных данных записаны три целых числа \(n, m, k\) (\(2 \leq n \leq 2000, 1 \leq m \leq 2000, 0 \leq k \leq 10\)) — количество вершин графа, количество ребер и параметр \(k\) соответственно.

В следующей строке содержится \(n\) целых чисел \(a_i\) (\(0 \leq a_i \leq 10^9\)) — начальные значения в вершинах.

В следующих \(m\) строках содержатся пары чисел \(u_i, v_i\) (\(1 \leq u_i, v_i \leq n\)) — вершины, соединенные \(i\)-м ребром. Гарантируется, что граф связный, в нем нет петель и кратных ребер.

Формат выходных данных
В единственной строке выходных данных выведите ответ на задачу.

Примечание

В первом тестовом примере одним из оптимальных способов получения ответа может быть изменение значения в вершине с номером \(2\) с числа \(15\) на число \(3\). В таком случае путь \(1 \rightarrow 2 \rightarrow 5 \rightarrow 6\) будет иметь стоимость \(|1 - 3| + |3 - 4| + |4 - 10| = 9\).

Второй пример отличается от первого лишь значением \(k\). Во втором примере можно поменять значения записанные в вершинах с номерами \(2, 3, 6\) на \(1\). Тогда стоимостью пути станет \(|1 - 1| + |1 - 1| + |1 - 1| + |1 - 1| = 0\).

графы дп кратчайшие пути

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

50111#50111

В реальных компьютерных сетях также используется понятие максимальной единицы передачи (MTU, maximum transmission unit) - размер блока данных, который может быть передан на отрезке сети между двумя устройствами. Этот размер зависит от ограничений используемой технологии
передачи данных на нижнем уровне.
В данной задаче требуется составить оптимальный план передачи пакетов с учётом MTU между разными маршрутизаторами и вычислить минимальное время передачи на его основе.
Нужно иметь в виду, что окно передачи работает по "скользящему" принципу, то есть после получения подтверждения доставки первых байтов окна оно сдвигается вправо на размер доставленной информации.

Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), время передачи до следующего маршрутизатора в миллисекундах и MTU в байтах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.

Выходные данные
Минимальное время передачи в миллисекундах.
Примечание: считать, что между получением каждого пакета и отправкой подтверждения с конечного устройства всегда проходит 1 мс.
Примечание 2: считать, если объём данных, который требуется отправить с одного маршрутизатора на другой, превышает MTU, то данные делятся на пакеты, равные максимальной единице передачи или меньше, и отправляются с задержкой в 1 мс.
В рамках данной задачи считать, что потери отсутствуют и все отправленные пакеты достигают получателя, а также что размер окна фиксированный и составляет 10240 байт. Также следует пренебречь временем передачи данных между конечными узлами и ближайшими
маршрутизаторами и размером пакета ACK (считать, что он меньше любого MTU).

Примеры

№	Входные данные	Выходные данные
1	5 3 10.0.0.0 8 2 10 100 20.0.0.0 8 3 10 100 10.0.0.0 8 5 10 10240 1 10.0.0.0 8 4 10 100 1 30.0.0.0 8 4 10 100 1 40.0.0.0 8 1 10 100 1 10.0.0.0 8 4 20 10240 40.1.1.1 1 10.1.1.1 4 102400	410

Примечание
Если отправлять пакеты с 1-го маршрутизатора на 5-й, то время передачи каждых 10240 байт с учётом подтверждения займёт 41 мс. Если же отправлять с 1-го через 2-й, то 10240 байт окна передачи будут делиться на 103 блока и суммарное время доставки для первого окна
увеличится до 133 мс, а для всего объёма данных - более 1000 мс.

кратчайшие пути реализация

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

50105#50105

Для передачи пакетов в глобальной компьютерной сети используются специальные устройства - маршрутизаторы. Они подключены к нескольким линиям связи и на основе содержащихся в их памяти таблиц маршрутизации определяют, по какому из направлений передавать приходящие пакеты.
IPv4 - 4-я и первая, получившая широкое распространение, версия протокола IP (Internet Protocol).
Адреса в этой версии представляют собой 4 октета - блока по 8 бит. В человекочитаемом представлении адреса принято записывать в форме 4-х десятичных чисел от 0 до 255, разделённых точками.
Поскольку маршрутизатор имеет несколько интерфейсов (физических разъёмов, куда подключены кабели связи), в таблице маршрутизации задано соответствие каждого интерфейса той или иной сети. Сеть определяется парой из IP-адреса и битовой маски (в которой N старших бит заполнены единицами, а 32-N младших заполнены нулями). Для проверки того, можно ли маршрутизировать
пакет в какую-либо сеть, битовая маска применяется к адресу сети и адресу узла назначения из пакета с помощью побитового И. Если получившийся результат совпадает, то пакет можно отправить на соответствующий интерфейс.
Протокол управления передачей TCP (transmission control protocol) - протокол более высокого уровня по сравнению с IP, предназначенный для доставки данных в неизменном виде. Для решения этой задачи в нём применяется ряд принципов, один из которых - подтверждение
получения данных. Для подтверждения от получателя к отправителю направляется специальный пакет с признаком ACK, в котором указан диапазон полученных байтов.
При этом для исключения перегрузок сети при передаче больших объёмов данных применяются "окна" передачи. Окном называется максимальный объём данных, который может быть отправлен от отправителя получателю без подтверждения получения. По мере подтверждения получения данных окно смещается вправо и отправляются новые данные.

Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел
указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), и время передачи до следующего маршрутизатора в миллисекундах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.

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

Примечание
102400 = 10240*10, значит, для передачи данных потребуется 10 итераций (сдвигов окна передачи). Каждые 10 Кбайт будут проходить следующую цепочку: отправка с первого маршрутизатора на второй - 10мс, затем со 2-го на 4-й ещё 10 мс, затем 1 мс задержки на
отправку подтверждения и сама передача подтверждения напрямую с 4-го маршрутизатора на 1-й - ещё 10 мс. Таким образом, на передачу каждых 10 Кбайт будет уходить 31 мс.

кратчайшие пути реализация

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

Космолёт#39627

Миссия космолёта “Юрий Гагарин” определена - посещение трех звёздных систем в глубоком космосе. Эти звёзды находятся на Земном небосводе в созвездии Орион:

звезда Беллатрикс (250 световых лет от Земли)
звезда Бетельгейзе (643 световых года от Земли)
парная звёздная система Ригель (773 световых года от Земли)

Маршрут путешествия должен предусматривать посещение их в порядке удаления от Земли. Однако гиперсветовой прыжок не может пока быть выполнен с приемлемой точностью на расстояние 20 и более световых лет. Спланированная трасса полёта должна состоять из серии
прыжков, каждый прыжок менее безопасного расстояния. Вторым ограничением является то, что промежуточные точки трассы должны находиться в окрестности массивного тела, т.е. звезды. Такие звёзды в навигации называются контрольными пунктами.
Необходимо учитывать, что управление выходом из гиперпространства невозможно без существенного искривления его в точке назначения гравитационным воздействием звезды контрольного пункта. Эта особенность налагает дополнительное ограничение на каждый
выполняемый гиперпрыжок: траектория прыжка не должна проходить меньше одного светового года от звёздной системы, не являющейся контрольным пунктом.
Задача : построить трассу в трёхмерном пространстве с минимально возможным количеством гиперпрыжков, при соблюдении указанных выше ограничений. Если таких трасс несколько, то следует выбрать ту, в которой суммарная длина трассы меньше.

Входные данные
Первая строка : натуральное число N - количество звезд, внесённых в лоцию (от 3 до 100).
Далее N строк, каждая содержит три целых числа, записанных через пробел: координаты X Y Z, заданные в световых годах. Все значения координат не превышают 10000. Точка старта (0 0 0) - звезда Солнце - не указана в лоции.
Три посещаемые звёздные системы находятся в лоции в порядке ожидаемого посещения, в строках с номерами 1, 2 и 3.

Выходные данные
Первая строка: через пробел должны быть указаны количество прыжков и длина трассы с точностью до третьего знака после запятой.
Вторая строка: номера звёзд-”контрольных пунктов” и звёзд-”целей миссии” в порядке следования звездолёта, записанные через пробел.
Примечание: для отработки алгоритма построения маршрута космолёта в лоцию (комплект навигационной информации для судовождения) могут включаться различные произвольные координаты, не соответствующие известным звёздам.
В рамках задачи считать, что движение космолёта между контрольными точками происходит прямолинейно.

Примеры

№	Входные данные	Выходные данные
1	3 10 10 10 20 20 20 30 30 30	3 51.962 1 2 3
2	5 20 0 0 10 0 0 40 0 0 30 0 0 50 0 0	4 40.000 2 1 4 3

графы кратчайшие пути реализация

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

Все кратчайшие маршруты#33229

Учёный-ботаник получил карту дорог страны Лимония. Чтобы составить план исследования этой страны, ему требуется найти кратчайшие расстояния между каждой парой городов этой страны (можно ехать только по проложенным дорогам). Помогите учёному – напишите программу, которая решает эту задачу.

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

В первой строке вводится количество городов N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог между городами: положительное число означает расстояние между городами, ноль говорит о том, что дороги нет.

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

Программа должна вывести все кратчайшие маршруты между всеми городами в следующем формате:

(1->3): 1 2 3 (23)

Сначала выводятся номера начального и конечного города (в скобках), затем – последовательность номеров городов, составляющая оптимальный маршрут, затем (в скобках) длина этого маршрута. Если между какими-то городами нет дороги, нужно вывести число 0.

Ввод	Вывод
4 0 0 0 0 0 0 2 1 0 2 0 4 0 1 4 0	(1,2): 0 (1,3): 0 (1,4): 0 (2,3): 2 3 (2) (2,4): 2 4 (1) (3,4): 3 2 4 (3)

Алгоритм Флойда кратчайшие пути

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

33228#33228

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

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

В первой строке вводится количество деревень N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог: положительное число означает расстояние между деревнями, ноль говорит о том, что дороги нет. В последней строке вводится N чисел - количество школьников в каждой деревне.

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

Программа должна вывести два числа: сначала номер деревни, где нужно построить школу, а затем (через пробел) – общее расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне.

Ввод	Вывод
4 0 11 8 4 11 0 2 5 8 2 0 13 4 5 13 0 15 26 30 12	2 255

Алгоритм Флойда кратчайшие пути

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

Авиаперелеты#27275

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

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

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

В первой строке находятся числа N (количество городов), M (количество авиарейсов), K (количество оставшихся ночей), S (номер города, в котором живет профессор), F (номер города, в котором проводится конференция).

Ограничения: 2≤N≤100, 1≤M≤10⁵, 1≤K≤100, 1≤S≤N, 1≤F≤N.

Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит три натуральных числа: S_i, F_i и P_i, где S_i - номер города, из которого вылетает i-й рейс, F_i- номер го-рода, в который прилетает i-й рейс, P_i - стоимость перелета i-м рейсом. 1≤S_i≤N, 1≤F_i≤N, 1≤P_i≤106.

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

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

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

Алгоритм Форда-Беллмана кратчайшие пути

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

Pink Floyd#27233

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤10⁴, 2≤k≤10⁴). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами b_i, e_i и w_i - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤b_i,e_i≤n, −10⁵≤w_i≤10⁵). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.

Ввод	Вывод
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 -10 1 3 1 2 4	6 5 6 5 7 2 3
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 10 1 3 1 2 4	infinitely kind

Алгоритм Флойда графы кратчайшие пути

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

Опасный маршрут#27232

Профессор Флойд живёт в очень опасном районе города. Ежедневно бандиты грабят на улицах прохожих. Читая криминальную хронику, профессор Флойд вычислил вероятность быть ограбленным при проходе по каждой улице города.

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

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

В первой строке находятся два числа N и M - количество зданий и количество улиц, соединяющих здания (1<=N<=100, 1<=M<= (N*(N−1))/2. В следующей строке находятся числа S и E -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в M строках расположены описания дорог: 3 целых числа sieipi - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (1<=s_i, e_i<=N, 0<=p_i<=100 , дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.

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

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

Ввод	Вывод
3 3 1 3 1 2 20 1 3 50 2 3 20	0.36

Алгоритм Дейкстры кратчайшие пути

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

Столовая#27231

Сегодня у студентов праздник! В одном из новых зданий университета решили открыть столовую. Для этих целей требуется выбрать одно из зданий, в котором и будет располагаться столовая. Чтобы студенты как можно меньше отвлекались от учёбы, было решено выбрать такое здание, чтобы максимальное расстояние от него до всех остальных зданий было как можно меньше.

Помогите найти такое здание!

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

В первой строке находятся два числе N и M - количество зданий и количество дорог, соединяющих здания (1<=N<=100, 0 <=M<=(N(N−1))/2. Далее в M строках расположены описания дорог: 3 целых числа s_i, e_i, l_i - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1<=s_i,e_i<=N, 0<=l_i,=100, дороги двунаправленные).

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

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

Ввод	Вывод
3 2 1 2 1 2 3 2	2
3 1 1 2 10	1

Алгоритм Флойда кратчайшие пути

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

Транзитивное замыкание#27229

Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в i-й строке и j-м столбце находится 1, если от вершины i можно добраться до вершины j, и 0 - иначе.

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

В первой строке дано число N (1<=N<=100) - число вершин в графе. Далее задана матрица смежности графа: в N строках даны по N чисел 0 или 1 в каждой. i-е число в i-й строке всегда равно 1.

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

Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.

Ввод	Вывод
4 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1	1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1

графы кратчайшие пути поиск в глубину и подобное

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

Флойд №2#27227

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

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

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

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

Выведите искомое максимальное кратчайшее расстояние.

Ввод	Вывод
6 0 6 8 -1 -1 -1 5 0 5 -1 -1 -1 1 7 0 -1 -1 -1 -1 -1 -1 0 6 -1 -1 -1 -1 -1 0 3 -1 -1 -1 2 -1 0	9

Алгоритм Флойда кратчайшие пути

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

Дейкстра: кратчайший путь через наибольшее число узлов#27208

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

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

В первой строке содержатся два числа: N, F (1≤N≤100, F≤N), где N – количество вершин графа, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

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

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

Ввод	Вывод
3 1 0 1 1 4 0 1 2 1 0	2 3 1

Алгоритм Дейкстры кратчайшие пути

—Войти и решать

Метро#23399

В мегаполисе, испытывающем большие транспортные проблемы, построили легкое метро. Оно состоит из 6 радиальных линий, которые расходятся от центра города, и k кольцевых линий в форме правильных шестиугольников. Станции метро располагаются на пересечении кольцевых и радиальных линий. На любой станции разрешено делать пересадки с кольцевых линий на радиальные и обратно. Радиальные линии последовательно нумеруются по часовой стрелке от 1 до 6. Кольцевые линии нумеруются от центра города (центр считается кольцевой линией с номером ноль, состоящей из одной станции).

Расстояние между двумя соседними станциями на одной радиальной линии равно 1 км. Расстояние между соседними станциями на кольцевой линии с номером i составляет i км. Любая станция обозначается парой чисел - номером радиальной линии r (\(1<=r<=6\)) и номером кольцевой линии k (\(0<=k<=32000\)), на пересечении которых она находится.

Напишите программу, определяющую длину кратчайшего пути между станциями.

Входные данные: Вводятся четыре числа: r1, k1, r2, k2 - координаты начальной и конечной станции.

Выходные данные: Необходимо вывести расстояние (в км), которое потребуется проехать пассажиру, чтобы попасть c начальной станции на конечную.

Примеры

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

кратчайшие пути Разбор случаев

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

Безопасный путь#21819

Петя и Вася — хорошие друзья. Поэтому они часто ездят друг к другу в гости. Недавно Петя

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

все дороги в городе, в котором они живут, являются бесконечными прямыми. В месте пересечения

двух или более дорог находятся перекрестки. Дома Пети и Васи расположены возле некоторых

дорог города, но не на перекрестках.

Петя начинает путь на дороге возле своего дома. При этом он может выбрать любое из

двух направлений. Когда Петя подъезжает к перекрестку, он может повернуть на любую другую

проходящую через него дорогу или продолжить ехать по текущей. Поскольку Петя не очень

опытный водитель, каждый поворот, который он совершает, заставляет его волноваться. Причем

волнение Пети равно величине угла, на который он поворачивает, в градусах. Например, при

повороте на прямой угол волнение Пети равно 90.

При менее крутом повороте Петя волнуется меньше, а при более крутом — сильнее.

Будем считать, что волнение Пети в течении всего маршрута равно сумме величин в

градусах углов, на которые ему придется повернуть в течении движения. Конечно, Петя хочет

воспользоваться маршрутом, который заставит его волноваться как можно меньше.

Помогите Пете выяснить, чему равно минимальное суммарное волнение, которое он испытает,

добравшись до дома Васи.

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

В первой строке входного файла находится целое число n (1 ≤ n ≤ 50) — количество дорог в

городе. В следующих n строках находится описание дорог.

Каждая дорога описывается четверкой целых чисел x1, y1, x2, y2, которые задают координатами

двух различных точек (x1, y1) и (x2, y2), через которые проходит дорога.

Гарантируется, что никакие две дороги не совпадают. В следующих двух строках заданы

координаты домов Пети и Васи. Гарантируется, что каждый дом находится ровно на одной дороге,

а также, что Петя и Вася живут в разных местах.

Координаты всех точек во входном файле являются целыми числами и не превосходят 100 по

абсолютному значению.

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

В выходной файл выведите единственное число — суммарный угол в градусах, на который

придется повернуть Пете при оптимальном выборе маршрута. Ответ считается правильным, если

его относительная или абсолютная погрешность не превосходит 10−9.

Если Петя никак не сможет добраться до дома Васи, выведите число −1.

Примеры
Ввод

0 0 2 0

1 1 0 2

1 2 3 2

-3 0

3 2
Вывод
270.0

Ввод

0 0 2 0

0 0

2 0
Вывод
0.0

Ввод

0 0 1 0

0 0 1 1

0 0 0 1

0 0 -1 1

0 1 1 1

5 0

0 5
Вывод
90.0

Следующий рисунок соответствует первому примеру. Петя совершает два поворота на 135

градусов, его суммарное волнение равно 270.

геометрия графы кратчайшие пути

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