Problem A. Dijkstra
Statement
You are to write a program that receives a weighted directed graph and finds
distances from source vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W.
Length of path is the sum of weights of its edges.
Vertices are numbered with integers from 1 to N.
Input file format
First line of input file contains three integers
N M and
S,
where
M is the number of edges. Next
M lines contain three
integers each —
starting vertex number, ending vertex number and weight of some edge respectively.
All weights are positive.
There is at most one edge connecting two vertices in every direction.
Output file format
Output file must contain
N integers — distances from
source vertex to all vertices.
If some vertices are not reachable from
S, corresponding numbers must be −1.
Constraints
1 ≤ N ≤ 1000.
All weights are less or equal than 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
5 3 1
1 2 5
1 3 7
3 4 10
|
0 5 7 17 -1
|
Задача B. Топологическая сортировка
Условие
Дан ориентированный ациклический граф. Требуется выполнить топологическую
сортировку его вершин. При этом сначала требуется вывести группу вершин, в которые
не входит ни одного ребра, затем вершины, в которые входят только
рёбра из вершин первой группы, затем те, в тоторые входят только рёбра из вершин
первой и второй групп и т.д. В каждой группе
номера вершин должны быть отсортированы по возрастанию.
Формат входного файла
Сначала указывается количество вершин
V и количество ребер
E.
Далее перечисляется
E пар вершин
(
vi,
vj), задающих ребра. Никакая пара
вершин не встречается дважды.
Формат выходного файла
Необходимо перечислить
V вершин в описанном порядке.
Ограничения
1 <=
V <= 1000000, 0 <=
E <= 1000000
1 <=
vi <=
V
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
6 5
2 3
4 6
3 1
5 1
2 5
|
2 4 3 5 6 1
|
Problem C. Eulerian cycle
Statement
You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.
Input file format
Input file contains two integers
N,
M.
Vertices are numbered with integer numbers from
1 to
N.
M is the number of edges. Each of following
M lines contains a pair of
vertex numbers, connected by some edge. There is at most one edge connecting two vertices.
Output file format
Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle.
If there does not exist any Eiler cycle, output file must contain
−1.
Constraints
1 ≤ N, M ≤ 100000
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 3
1 2
2 3
3 1
|
1 2 3 1
|
Задача D. Домой на электричках
Условие
Одна из команд-участниц олимпиады решила вернуться домой на электричках.
При этом ребята хотят попасть домой как можно раньше.
К сожалению, не все электрички идут от города, где проводится олимпиада, до станции,
на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции,
останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях,
мимо которых они идут).
Все станции на линии пронумерованы числами от 1 до N.
При этом станция номер 1 находится в городе, где проводится олимпиада,
и в момент времени 0 ребята приходят на станцию.
Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время,
за которое ребятам удастся добраться домой.
Формат входного файла
Во входном файле записаны сначала числа
N и
E.
Затем записано число M, обозначающее число рейсов электричек.
Далее идет описание M рейсов электрички.
Описание каждого рейса электрички начинается с числа
Ki — количества станций,
на которых она останавливается, а далее следует
Ki пар чисел,
первое число каждой пары задает номер станции, второе — время
(время выражается целым числом из диапазона от 0 до 10
9).
Станции внутри одного рейса упорядочены в порядке возрастания времени.
В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
Формат выходного файла
В выходной файл выведите одно число - минимальное время,
когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они
добраться не смогут, выведите -1.
Ограничения
2 ≤ E ≤ N ≤ 1000,
1 ≤ M ≤ 100,
2 ≤ Ki ≤ N.
Примеры тестов
| № |
Входной файл (a.in) |
Выходной файл (a.out) |
|---|
| 1 |
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
|
20
|
