Skip to content

Latest commit

 

History

History
 
 

hw11

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 

Графы-2. Кратчайшие пути

A. Приключения шахматного коня

Ограничение по времени на тест: 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

B. Кратчайший путь -- 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

C. Цикл отрицательного веса

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

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

Входные данные

Во входном файле в первой строке число N (1 ≤ N ≤ 100) — количество вершин графа. В следующих N строках находится по N чисел — матрица смежности графа. Все веса ребер не превышают по модулю 10 000. Если ребра нет, то соответствующее число равно 100 000.

Выходные данные

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

Пример

Входные данные

2
0 -1
-1 0

Выходные данные

YES
2
2 1

D. Кратчайшие пути

Ограничение по времени на тест: 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
-
-
-
*