README.md

Графы, кратчайшие пути

A. Флойд

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

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

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

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

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

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

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

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

Выведите N строк по N чисел — матрицу расстояний между парами вершин, где j-ое число в i-ой строке равно весу кратчайшего пути из вершины i в j.

Примеры

входные данные

4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0

выходные данные

0 5 7 13 
12 0 2 8 
11 16 0 7 
4 9 11 0 

Решение

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. Кратчайший путь длины K

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

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

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

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

Дан ориентированный граф. Найдите кратчайшие пути, состоящие из K рёбер, от S до всех вершин.

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

В первой строке дано целых четыре целых числа: 1 ≤ N, M ≤ 10^4 — количества вершин и рёбер, 0 ≤ K ≤ 100 — количество рёбер в кратчайших путях, 1 ≤ S ≤ N — начальная вершина.

В последующих M строках даны тройки целых чисел ai, bi, w — начало и конец ребра, а также его вес (1 ≤ ai, bi ≤ N,  - 10^5 ≤ w ≤ 10^5).

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

Выведите ровно N чисел по одному в строке. i-е число — длина минимального пути из ровно K рёбер из S в i, или  - 1, если пути не существует.

Примеры

входные данные

3 3 1 1
1 2 100
2 3 300
1 3 2

выходные данные

-1
100
2

входные данные

3 3 2 1
1 2 100
2 3 300
1 3 2

выходные данные

-1
-1
400

Решение

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

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

Решение

F. В поисках утраченного кефира

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

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

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

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

Школьник Вася хочет найти запасы спрятанного кефира. По легенде, кефир находится в домиках a, b или c. Вася хочет проверить каждый из этих трёх домиков, потратив на это минимальное количество времени.

Местность, в которой находится Вася представляет собой n домиков, пронумерованных числами от 1 до n. Некоторые из домиков соединены дорогами, по которым можно ходить в обе стороны. Время прохождения i-й дороги составляет wi секунд. Путём в графе называется непустая последовательность вершин, такая что все соседние вершины соединены дорогой. Требуется помочь Васе найти путь, содержащий вершины a, b, c, такой что суммарное время прохождения всех дорог на пути минимально. При этом, если мы прошли по какой-то дороге дважды (или более), то и время её прохождения следует учитывать соответствующее количество раз. Начинать свой путь Вася может из любой вершины.

Гарантируется, что a, b, c — попарно различные домики.

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

В первой строке ввода записаны два числа n и m (3 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000) — количество домиков в ЛКШ и дорог между ними соответственно.

Следующие m строк содержат описания дорог, по одному в строке. Каждая из дорог задаётся тройкой чисел ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9) — номерами соединённых домиков и временем, затрачиваемым на прохождение данной дороги. По каждой дороге разрешено ходить в обе стороны. Гарантируется, что любая пара домиков соединена не болee чем одной дорогой. Также гарантируется, что нет дороги, соединяющей домик с самим собой.

В последней строке записаны три попарно различных числа a, b, c (1 ≤ a, b, c ≤ n).

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

Выведите одно целое число — минимальное возможное время, которое нужно затратить на прохождение пути, содержащего домики a, b и c. Если пути, содержащего все три домика не существует, то выведите -1.

Примеры

входные данные

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

выходные данные

11

входные данные

4 2
1 2 10
2 3 5
1 2 4

выходные данные

-1

Примечание

В первом примере путь 1–2–3–4 является минимальным (11 секунд). Например, путь 1–2–4–3 не подходит, так как занимает больше времени (20 секунд), а путь 3–4–2 не подходит, так как домик a оказывается не посещенным.

Во втором примере не существует способа добраться от домика b до домика c, поэтому искомого пути не существует.

Решение

G. Бемби

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

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

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

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

Существует страна, в которой n городов. Города пронумерованы от 1 до n. Также в этой стране существуют двунаправленные дороги. Каждая дорога соединяет пару городов. Для каждого i, автомобильная дорога i соединяет города ai и bi.

Бемби — это олень, который любит путешествовать по дорогам. Движение по дороге i (в любом направлении) занимает у оленя di минут. Бемби ненавидит города и из-за этого никогда в них не задерживается.

Бемби начинает путешествие из города номер 1. Через t минут он желает оказаться в городе n. Вы должны узнать, может ли Бемби достигнуть город n ровно через t минут.

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

Первая строка содержит два целых числа n и m — количество городов и дорог в стране (1 ≤ n, m ≤ 50).

Следующие m строк описывают дороги. Каждая строка состоит из чисел ai, bi и di — концы дороги и ее длина (1 ≤ ai, bi ≤ n; 1 ≤ di ≤ 10^4).

Последняя строка содержит целое число t — количество минут, за которое Бемби желает добраться до города n (1 ≤ t ≤ 10^18).

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

Выведите "Possible" если Бемби сможет достичь цели ровно за t минут, иначе выведите "Impossible".

Примеры

входные данные

3 3
1 3 7
1 2 6
2 3 5
11

выходные данные

Possible

входные данные

3 3
1 3 7
1 2 6
2 3 5
25

выходные данные

Possible

входные данные

2 1
1 2 1
9

выходные данные

Possible

входные данные

2 1
2 1 1
1000000000000000000

выходные данные

Impossible

входные данные

4 3
1 3 10
1 2 10
2 3 10
1000

выходные данные

Impossible

H. Карликовая башня

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

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

ввод: dwarf.in

вывод: dwarf.out

Маленький Вася играет в новую игру, которая называется «Карликовая башня». В этой игре есть n различных предметов, которые можно надеть на героя. Предметы занумерованы числами от 1 до n. Вася хочет получить предмет с номером 1. Есть два способа получить предмет: • Можно купить предмет. i-й предмет стоит ci денег. • Можно изготовить предмет. Эта игра поддерживает только m типов производства. Чтобы произвести предмет, нужно отдать два различных предмета и получить один в качестве результата. Помогите Васе потратить минимальное количество денег, чтобы получить предмет с номером 1.

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

Первая строка содержит два целых числа n и m (1 ⩽ n ⩽ 10 000; 0 ⩽ m ⩽ 100 000) — количество различных предметов и типов производства, соответственно. Вторая строка содержит n целых чисел ci — стоимости предметов (0 ⩽ ci ⩽ 10^9). Следующие m строк описывают типы производства, каждая строка состоит из трех различных целых чисел ai, xi, yi — предмет ai можно получить из предметов xi и yi (1 ⩽ ai, xi, yi ⩽ _n; ai ̸= xi; xi ̸=yi; yi ̸= ai).

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

Выведите одно целое число: минимальное количество денег.

Примеры

входные данные

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

выходные данные

2

Решение