Problem A. Ford-Bellman ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3 1
1 2 5
1 3 10
2 3 2

0 5 7

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

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 250

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

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

2
0 -1
-1 0

YES
3
1 2 1

Problem C. Floyd-Warshall ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 5
1 3 10
2 3 2

0 5 7
  0 2
    0

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

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Problem E. Fast Dijkstra ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• S — остаться на месте;
• U — сдвинутся на одну клетку вверх;
• R — сдвинутся на одну клетку вправо;
• D — сдвинутся на одну клетку вниз;
• L — сдвинутся на одну клетку влево.

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

Ограничения

1 ≤ n, m ≤ 500;

1 ≤ i_r ≤ n;

2 ≤ j_r ≤ m;

1 ≤ h_i,j ≤ 10⁵ при j > 2;

h_i,1 = 0;

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

3 3 2 3
0 5 5
0 5 5
0 1 1

DDRR

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

4 2 2 2
0 1
0 1
0 2
0 3

NO

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

Условие

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

В базе данных компании содержатся N городов, пронумерованных от 1 до N, и M односторонних дорог между некоторыми из них. Дорога номер i характеризуется тремя числами u_i v_i l_i — начальным городом, конечным городом и длиной дороги. Гарантируется, что u_i ≠ v_i, и не существует двух разных дорог i, j, для которых u_i = u_j, v_i = v_j.

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

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

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

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

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

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

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

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

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

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

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