Problem A. Ford-Bellman

Author:StdAlg   Time limit:0.2 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

Задача B. Цикл отрицательного веса

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

Формат входных данных

Во входном файле в первой строке число n  — количество вершин графа. В следующих n строках находится по n чисел — матрица смежности графа. Если ребра нет, то соответствующее число равно 109.

Формат выходных данных

В первой строке выходного файла выведите YES, если цикл существует или NO в противном случае. При его наличии выведите во второй строке количество вершин в искомом цикле (считая одинаковые первую и последнюю) и в третьей строке — вершины, входящие в этот цикл в порядке обхода.

Ограничения

1 ≤ n ≤ 250

Все веса ребер не превышают по модулю 10000

Примеры тестов

Стандартный вход Стандартный выход
1
2
0 -1
-1 0
YES
3
1 2 1

Problem C. Floyd-Warshall

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

Statement

You are to write a program that finds shortest distances between all pairs of vertices in a directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N and M, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a matrix of size NxN. Element in the j-th column of i-th row mush be the shortest distance between vertices i and j. The distance from the vertex to itself is considered to be 0. If some vertex is not reachable from some other, there must be empty space in corresponding cell of matrix.

Constraints

0 ≤ N ≤ 100. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 5
1 3 10
2 3 2
0 5 7
  0 2
    0

Problem D. 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

Problem E. Fast Dijkstra

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

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

Задача F. Дед Мазай и зайцы

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дед Мазай давно живёт в деревне Малые Вежи. Так давно, что он составил карту высот окрестностей.

Карта представляет собой прямоугольник n × m клеток (n клеток в высоту и m клеток в ширину). Для клетки, находящейся в i-ом ряду на j-ой колонке, отмечена высота hi,j местности в этой клетке над уровнем реки (в метрах). Известно, что для всех i выполняется соотношение hi,1 = 0. То есть, изначально рекой затоплены те и только те клетки, которые располагаются в самом левом столбце карты.

На реке начался паводок. Уровень реки поднимается на 1 метр каждую минуту, затопляя окрестности. А именно, если клетка (i, j) соседствует с клеткой, затопленой рекой, и уровень реки уже достиг или превысил hi,j, то считается, что клетка (i, j) также затоплена рекой. Клетки считаются соседними, если у них имеется одна общая сторона.

В начале паводка дед Мазай в своей лодке находится в клетке (1; 1) — в левом верхнем углу карты. За одну минуту дед Мазай может перебраться на соседнюю клетку, если она уже затоплена рекой или будет затоплена рекой к моменту окончания перехода.

Зайцы в начале паводка располагаются в клетке (ir, jr), jr > 1. Обычно зайцы стоят на месте, но если на следующей минуте их клетка окажется затоплена рекой, то они пытаются перейти на соседнюю клетку, которая не будет затоплена рекой. Если таких клеток несколько, то они выбирают из них первую в следующем списке: верхняя, правая, нижняя, левая. Если соседних клеток, которые на следующей минуте не будут затоплены рекой, не существует, то зайцы утонут.

Дед Мазай стремится спасти зайцев. Если он оказывается на клетке, соседней с зайцами, то они все оказываются спасены, даже если через минуту их клетка окажется затоплена рекой. При спасении клетка с зайцами не должна быть затоплена рекой.

Вы находитесь в безопасности в доме Деда Мазая. Перед глазами у вас карта и вам известно, где находятся зайцы. У вас есть связь по рации с Дедом Мазаем. Сообщите ему поминутный список перемещений, которые надо совершить, чтобы спасти зайцев; либо сообщите, что зайцев спасти невозможно. Если существует несколько решений, выведите любое из них. Решение должно заканчиваться позицией, в которой дед Мазай находится на соседней с зайцами клетке, и их клетка не затоплена рекой.

Зайцы никогда не выходят за пределы карты. Деду Мазаю также не разрешается выводить свою лодку за пределы карты.

В первом примере дед Мазай подплывает к зайцам через 4 минуты. Уровень реки в этот момент равен 4 метрам, и в следующую минуту река затопит всю местность. Зайцы оказываются спасены.

Во втором примере дед Мазай перемещается на одну клетку вправо и ждёт пока зайцы сами окажутся рядом с ним, спасаясь от потопа.

Во третьем примере, спасаясь от потопа, зайцы убегают в направлении от деда Мазая. Как бы дед Мазай ни действовал, он не успевает спасти зайцев.

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

В начале входного файла записаны целые числа n, m, ir, jr. Далее следует nm целых чисел hi,j — карта.

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

Если зайцев можно спасти, то выведите строку с инструкциями для деда Мазая. Каждый символ строки обозначает, что должен делать дед Мазай в очередную минуту:

Если зайцев спасти невозможно, выведите единственное слово "NO".

Ограничения

1 ≤ n, m ≤ 500;

1 ≤ ir ≤ n;

2 ≤ jr ≤ m;

1 ≤ hi,j ≤ 105 при j > 2;

hi,1 = 0;

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 2 3
0 5 5
0 5 5
0 1 1
DDRR
2
5 4 5 2
0 1 1 1
0 4 5 6
0 3 1 1
0 2 1 1
0 1 1 1
RSS
3
4 2 2 2
0 1
0 1
0 2
0 3
NO

Задача G. Грузоперевозки

Автор:Р. Данилов   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Стивен устроился на работу программистом в новую транспортную компанию. В его обязанности входит оптимизация стоимости грузоперевозок из одной страны в другую.

В базе данных компании содержатся N городов, пронумерованных от 1 до N, и M односторонних дорог между некоторыми из них. Дорога номер i характеризуется тремя числами ui vi li — начальным городом, конечным городом и длиной дороги. Гарантируется, что ui ≠ vi, и не существует двух разных дорог i, j, для которых ui = uj, vi = vj.

Страна представляет из себя такое множество из одного или более городов, что:

  1. из каждого города страны можно добраться в любой другой город этой страны по дорогам;
  2. ко множеству нельзя добавить ни одного города, сохранив при этом свойство 1.

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

Запрос на перевозку определяется парой чисел sj fj — номерами города отправления и города назначения j-го груза. Напишите программу, которая для каждого из Q запросов определяет наименьшую возможную стоимость перевозки груза.

В тесте из примера имеется две страны. Одна состоит из городов 1, 2, 3, другая — из городов 4, 5.

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

Входной файл содержит целые числа N M — количество городов и дорог соответственно.

Далее следует M троек целых чисел ui vi li — начальный город, конечный город и длина i-й дороги.

Далее следует целое число Q, за котором идут Q запросов по два целых числа sj fj — город отправления и город назначения j-го груза.

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

Выходной файл должен содержать Q целых чисел, каждое из которых равно наименьшей стоимости перевозки для соответствующего запроса, или  − 1, если эта перевозка невозможна.

Ограничения

1 ≤ N ≤ 300; 0 ≤ M ≤ N(N − 1); 1 ≤ Q ≤ 105; 1 ≤ ui, vi, sj, fj ≤ N; 0 ≤ li ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 6
1 2 1
2 3 3
3 1 3
1 4 2
4 5 1
5 4 2
4
2 5
1 3
4 1
1 1
2
0
-1
0

0.456s 0.011s 25