Problem A. Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

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. Топологическая сортировка

Автор:Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков   Ограничение времени:7 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

Сначала указывается количество вершин 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

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

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. Домой на электричках

Автор:X командный чемпионат Санкт-Петербурга по программированию - V Открытая Кировская командная олимпиада   Ограничение времени:2 сек
Входной файл:a.in   Ограничение памяти:8 Мб
Выходной файл:a.out  

Условие

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

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

Формат входного файла

Во входном файле записаны сначала числа N и E. Затем записано число M, обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

Формат выходного файла

В выходной файл выведите одно число - минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите -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

0.089s 0.006s 17