Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

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

Заправки-2

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

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

Входные данные
В первой строке вводится число N (1<=N<=100), в следующей строке идет N чисел, i-е из которых задает стоимость бензина в i-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.
 
Выходные данные
Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.
 
Ввод Вывод
4
1 10 2 15
4
1 2
1 3
4 2
4 3
2

Источник: http://informatics.mccme.ru/mod/statements/view3.php?id=257&chapterid=113213#

Заправки

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

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

Ввод Вывод
5
3 6 1 7 6 
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
3

Автобусы

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

Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.
 
Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).
 
Входные данные
Сначала вводится число N – общее число деревень (1 <= N <= 100),  затем номера деревень d и v,  за ними следует количество автобусных рейсов R (0 <= R <= 10000). Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000). Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.
 
Выходные данные
Выведите минимальное время, когда Мария Ивановна может оказаться в деревне v. Если она не сможет с помощью указанных автобусных рейсов добраться из d в v, выведите -1.

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

Защищенное соединение

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

В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании «Laim.UR» и «Xenda» решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании n городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.
Специалисты компаний определили m пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

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

Формат входных данных
В первой строке находятся целые числа n и m (2 ≤ n ≤ 5 000, 1 ≤ m ≤ 105 ) — количество городов и количество пар городов, которые можно соединить сегментом канала связи. Во второй строке находятся n целых чисел ai (0 ≤ ai ≤ 2). Если ai = 0, то в i-м городе нет дата-центра ни одного из гигантов. Если ai = 1, то в i-м городе есть дата-центр «Laim.UR», а если ai = 2, то в i-м городе находится дата-центр «Xenda». Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка. В каждой из следующих m строк находится по три целых числа — si , ti и ci , которые означают, что города si и ti (1 ≤ si , ti ≤ n, si != ti) можно соединить сегментом канала связи стоимостью ci (1 ≤ ci ≤ 105 ). Каждую пару городов можно соединить не более чем одним сегментом канала.

Формат выходных данных
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: x, y и d, означающие, что между городами x и y возможно провести канал связи суммарной стоимостью d. В городе x должен находиться дата-центр «Laim.UR», в городе y — дата-центр «Xenda». Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите −1.

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

Пояснение
В первом примере оптимально построить канал связи из двух сегментов: 3 − 2 и 2 − 4.