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

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 больше, чем исходный кратчайший маршрут.

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

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

Злой лифт#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—Войти и решать

Дейкстра: кратчайший путь через наибольшее число узлов#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

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

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