Problem A. SST for sparse graph
Statement
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
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 next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 3
1 2 10
2 3 10
3 1 10
|
20
|
Problem B. Fast Dijkstra
Statement
You are to write a program that receives a weighted directed graph and finds
all distances from fixed 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 arcs.
Input file format
Input file contains two integers N, M and S.
Vertices are numbered with integer numbers from 1 to N. S is the number of
source vertex. M is the number of arcs. Each of next M lines contain three
integers — numbers of starting and ending vertices of some arc and its weight
respectively. All weights are positive. There is at most one arc connecting
two vertices in every direction.
Output file format
Output file must contain N numbers. Each I-th number is the distance from
vertex S to vertex I. If some vertices are not reachable from S, corresponding
numbers must be −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 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
|
Задача C. Нормальное честное списывание
Условие
В группе школьников, состоящей из N человек (пронумерованных от 1 до N),
распостранено списывание домашних заданий.
Почерк большинства школьников неразборчив,
поэтому для каждого школьника известен набор его товарищей, почерк которых он может разобрать.
Чтобы не делать лишнюю работу, школьники договорились, что домашние задания
будет выполнять минимально необходимое число школьников.
У них будут списывать те, кто понимает их почерк.
И так далее, пока у всей группы не будет готовых домашних заданий.
Чтобы честно распределить работу, каждый день они выбирают другое множество выполняющих задание.
Найдите максимальное количество дней, в течение которого этот уговор может действовать
(т.е количество способов выбора школьников).
Формат входного файла
В первой строке входного файла содержатся числа
N M.
Далее следует
M пар чисел в диапазаоне от 1 до
N.
Пара
a b означает, что школьник с номером
b может списать у школьника с номером
a.
Формат выходного файла
Выходной файл должен содержать единственное целое число — количество способов.
Ответ должен быть выведен без лидирующих нулей.
В приведенном примере возможны три способа выбора школьников, удовлетворяющих условию:
{1,5},{2,5},{3,5}. Школьник 4 списывает в любой ситуации.
Ограничения
1 ≤ N ≤ 104,
0 ≤ M ≤ 105
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5 4
1 2
2 3
3 1
3 4
|
3
|
