- A Флойд
- B Кратчайший путь-2
- C Цикл отрицательного веса
- D Кратчайший путь длины $K$
- E Кратчайшие пути
- F В поисках утраченного кефира
- G Бемби
ограничение по времени на тест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
ограничение по времени на тест2 секунды
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Условие:
Дан неориентированный связный взвешенный граф. Найдите кратчайшее расстояние от первой вершины до всех вершин.
Входные данные:
В первой строке входного файла два числа: n и m (2 ≤ n ≤ 30000, 1 ≤ m ≤ 400000), где n — количество вершин графа, а m — количество ребер.
Выходные данные:
Выведите 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
ограничение по времени на тест4 секунды
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Условие:
Дан ориентированный граф. Найдите кратчайшие пути, состоящие из K рёбер, от S до всех вершин.
Входные данные:
В первой строке дано целых четыре целых числа: 1 ≤ N, M ≤ 104 — количества вершин и рёбер, 0 ≤ K ≤ 100 — количество рёбер в кратчайших путях, 1 ≤ S ≤ N — начальная вершина.
Выходные данные:
Выведите ровно 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
ограничение по времени на тест2 секунды
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Условие:
Вам дан взвешенный ориентированный граф и вершина s в нём. Для каждой вершины графа u выведите длину кратчайшего пути от вершины s до вершины u.
Входные данные:
Первая строка входного файла содержит три целых числа n, m, s — количество вершин и ребёр в графе и номер начальной вершины соответственно (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 5 000).
Выходные данные:
Выведите 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
-
-
-
*
ограничение по времени на тест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) — количество домиков в ЛКШ и дорог между ними соответственно.
Выходные данные:
Выведите одно целое число — минимальное возможное время, которое нужно затратить на прохождение пути, содержащего домики 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
ограничение по времени на тест2 секунды
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Условие:
Существует страна, в которой n городов. Города пронумерованы от 1 до n. Также в этой стране существуют двунаправленные дороги. Каждая дорога соединяет пару городов. Для каждого i, автомобильная дорога i соединяет города ai и bi.Бемби — это олень, который любит путешествовать по дорогам. Движение по дороге i (в любом направлении) занимает у оленя di минут. Бемби ненавидит города и из-за этого никогда в них не задерживается.Бемби начинает путешествие из города номер 1. Через t минут он желает оказаться в городе n. Вы должны узнать, может ли Бемби достигнуть город n ровно через t минут.
Входные данные:
Первая строка содержит два целых числа n и m — количество городов и дорог в стране (1 ≤ n, m ≤ 50).
Выходные данные:
Выведите "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