Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
На шахматной доске N × N в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?
На вход программы поступает пять чисел: N, x1, y1, x2, y2 (5 ≤ N ≤ 20, 1 ≤ x1, y1, x2, y2 ≤ N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя — (N, N).
В первой строке выведите единственное число K — количество посещенных клеток. В каждой из следующих K строк должно быть записано 2 числа — координаты очередной клетки в пути коня.
Входные данные
5
1 1
3 2
Выходные данные
2
1 1
3 2
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дан неориентированный связный взвешенный граф. Найдите кратчайшее расстояние от первой вершины до всех вершин.
В первой строке входного файла два числа: n и m (2≤ n ≤30000,1≤ m ≤400000), где n — количество вершин графа, а m — количество ребер.
Следующие m строк содержат описание ребер. Каждое ребро задается стартовой вершиной, конечной вершиной и весом ребра. Вес каждого ребра — неотрицательное целое число, не превосходящее 10^4.
Выведите n чисел — для каждой вершины кратчайшее расстояние до нее.
Входные данные
4 5
1 2 1
1 3 5
2 4 8
3 4 1
2 3 3
Выходные данные
0 1 4 5
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дан ориентированный граф. Определите, есть ли в нем цикл отрицательного веса, и если да, то выведите его.
Во входном файле в первой строке число N (1 ≤ N ≤ 100) — количество вершин графа. В следующих N строках находится по N чисел — матрица смежности графа. Все веса ребер не превышают по модулю 10 000. Если ребра нет, то соответствующее число равно 100 000.
В первой строке выходного файла выведите «YES», если цикл существует или «NO» в противном случае. При его наличии выведите во второй строке количество вершин в искомом цикле и в третьей строке — вершины входящие в этот цикл в порядке обхода.
Входные данные
2
0 -1
-1 0
Выходные данные
YES
2
2 1
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Вам дан взвешенный ориентированный граф и вершина s в нём. Для каждой вершины графа u выведите длину кратчайшего пути от вершины s до вершины u.
Первая строка входного файла содержит три целых числа n, m, s — количество вершин и ребёр в графе и номер начальной вершины соответственно (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 5 000).
Следующие m строчек описывают рёбра графа. Каждое ребро задаётся тремя числами — начальной вершиной, конечной вершиной и весом ребра соответственно. Вес ребра — целое число, не превосходящее 10^15 по абсолютной величине. В графе могут быть кратные рёбра и петли.
Выведите n строчек — для каждой вершины u выведите длину кратчайшего пути из s в u. Если не существует пути между s и u, выведите «*». Если не существует кратчайшего пути между s и u, выведите «-».
Входные данные
6 7 1
1 2 10
2 3 5
1 3 100
3 5 7
5 4 10
4 3 -18
6 1 -1
Выходные данные
0
10
-
-
-
*