Задачи с codeforses на 2 разные темы (ссылки для проверки приложены к каждой задаче)

Тема: Кратчайшие пути в графах

1. Издевательство

ограничение по времени на тест1 секунд
ограничение по памяти на тест256 мегабайт

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана. -Издевается! - подумал Борман. -Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби – он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

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


Входные данные
Во входных данных записано сначала число N (3 ≤ N ≤ 100), а затем матрица N × N расстояний между площадями (число в позиции i, j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

входные данные
5
0 20 10 30 40
20 0 30 1 2
10 30 0 40 1000
30 1 40 0 21
40 2 1000 21 0

выходные данные
2 4 5


ссылка для теста задачи:https://codeforces.com/group/50U9rD7F6W/contest/24...

2.Цикл
ограничение по времени на тест1 секунда ограничение
по памяти на тест 256 мегабайт

Дан взвешенный ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.


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

Выходные данные
Выведите "YES", если цикл существует, и "NO" в противном случае.

входные данные
2
0 -1
-1 0

выходные данные
YES

ссылка для теста задачи:https://codeforces.com/group/50U9rD7F6W/contest/24...


3.Автобусы
ограничение по времени на тест1 секунда
ограничение по памяти на тест 256 мегабайт

Между некоторыми деревнями Пермской области ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день (например, в Ляды из Перми автобус приходит лишь 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

ссылка для теста задачи:https://codeforces.com/group/50U9rD7F6W/contest/24...

Тема:СНМ, обходы графов

3.Михаил Густокашин против бюрократии
ограничение по времени на тест1 секунда
ограничение по памяти на тест 256 мегабайт

Задача классическая. Формулировка: Михаил Густокашин.

Как я уже писал, с 1 сентября 2002 года я буду учиться в СУНЦ МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того, чтобы я был допущен к занятиям, мне необходимо предъявить справку по форме 086/У, на которой должна поставить свои подписи K врачей.

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

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


Входные данные
В первой строке моего списка содержится общее количество врачей (1 ≤ K ≤ 100). В следующих K строках описываются необходимые справки. Первое число (j) в i + 1 строке входных данных означает, сколько справок нужно i-му врачу. Затем, в той же строке, содержится j чисел – номера врачей, чьи подписи надо предварительно поставить, чтобы получить подпись i-го врача.

Выходные данные
Если подписи всех врачей собрать невозможно, то следует вывести "NO". Если же все справки собрать возможно, то в первой строке должно содержаться "YES", а в следующих K строках – последовательность, в которой нужно получать справки.

входные данные
4
1 2
0
2 1 4
1 1
выходные данные
YES
2
1
4
3

ссылка для теста задачи:https://codeforces.com/group/50U9rD7F6W/contest/37...