Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
Программа получает сначала число N \((1 \leq N \leq 100)\) – количество вершин графа и число \(M (0 \leq M \leq 10000)\) – количество ребер. В следующих строках идет \(M\) троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).
Программа должна вывести \(N\) чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.
| Ввод | Вывод |
|---|---|
6 4 1 2 10 2 3 10 1 3 100 4 5 -10 |
0 10 20 30000 30000 30000 |
Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.
В первой строке содержится число \(N (1 \leq N \leq 100)\) – количество вершин графа. В следующих \(N\) строках находится по \(N\) чисел – матрица смежности графа. Веса ребер по модулю меньше 100000. Если ребра нет, соответствующее значение равно 100000.
В первой строке выведите "YES", если цикл существует, или "NO", в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые – первую и последнюю), а в третьей строке – вершины, входящие в этот цикл, в порядке обхода. Если циклов несколько, то выведите любой из них.
| Ввод | Вывод |
|---|---|
3 100000 100000 -51 100 100000 100000 100000 -50 100000 |
YES 4 3 2 1 3 |
Профессору Форду необходимо попасть на международную конференцию. Он хочет потратить на дорогу наименьшее количество денег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночевку в отелях), а днем будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелетов и составил набор подходящих авиарейсов, выяснив, что перелеты на выбранных направлениях совершаются каждую ночь и за одну ночь он не сможет совершить два перелета.
Теперь профессор хочет найти путь наименьшей стоимости, учитывая что до конференции осталось \(K\) ночей (то есть профессор может совершить не более \(K\) перелетов).
В первой строке находятся числа \(N\) (количество городов), \(M\) (количество авиарейсов), \(K\) (количество оставшихся ночей), \(S\) (номер города, в котором живет профессор), \(F\) (номер города, в котором проводится конференция).
Ограничения: \(2 \leq N \leq 100\), \(1 \leq M \leq 10^5\), \(1 \leq K \leq 100\), \(1 \leq S \leq N\), \(1 \leq F \leq N\).
Далее идет \(M\) строк, задающих расписание авиарейсов. \(i\)-я строка содержит три натуральных числа: \(S_i\), \(F_i\) и \(P_i\), где \(S_i\) - номер города, из которого вылетает \(i\)-й рейс, \(F_i\) - номер города, в который прилетает \(i\)-й рейс, \(P_i\) - стоимость перелета \(i\)-м рейсом. \(1 \leq S_i \leq N\), \(1 \leq F_i \leq N\), \(1 \leq P_i \leq 10^6\).
Выведите одно число - минимальную стоимость пути, подходящего для профессора. Если профессор не сможет за \(K\) ночей добраться до конференции, выведите число -1.
| Ввод | Вывод |
|---|---|
4 5 2 1 4 1 2 1 2 3 1 3 4 1 1 3 3 1 4 5 |
4 |
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
В первой строке вводится единственное число \(N (1 \leq N \leq 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 |
Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
В первой строке вводится единственное число \(N (1 \leq N \leq 100)\) – количество вершин графа. В следующих \(N\) строках по \(N\) чисел задается матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы – всегда нули.
Выведите искомое максимальное кратчайшее расстояние.
| Ввод | Вывод |
|---|---|
6 0 6 8 -1 -1 -1 5 0 5 -1 -1 -1 1 7 0 -1 -1 -1 -1 -1 -1 0 6 -1 -1 -1 -1 -1 0 3 -1 -1 -1 2 -1 0 |
9 |
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить, существует ли кратчайший путь между ними или нет.
Комментарий: Кратчайший путь может не существовать по двум причинам:
В первой строке входного файла записано единственное число: \(N (1 \leq N \leq 100)\) — количество вершин графа. В следующих \(N\) строках по \(N\) чисел — матрица смежности графа (\(j\)-е число в \(i\)-й строке соответствует весу ребра из вершины \(i\) в вершину \(j\)): число 0 обозначает отсутствие ребра, а любое другое число — наличие ребра соответствующего веса. Все числа по модулю не превышают 100.
Выведите \(N\) строк по \(N\) чисел. \(j\)-е число в \(i\)-й строке должно соответствовать кратчайшему пути из вершины \(i\) в вершину \(j\). Число должно быть равно 0, если пути не существует, 1, если существует кратчайший путь, и 2, если пути существуют, но бывают пути сколь угодно маленького веса.
| Ввод | Вывод |
|---|---|
5 0 1 2 0 0 1 0 3 0 0 2 3 0 0 0 0 0 0 0 -1 0 0 0 -1 0 |
1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 2 2 0 0 0 2 2 |
Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины \(s\) в вершину \(t\).
В первой строке заданы три числа: число вершин в графе \(N \leq 50\), номера вершин \(s\) и \(t\). Далее идёт матрица смежности графа, то есть \(N\) строк, в каждой из которых записано \(N\) чисел. \(j\)-ое число в \(i\)-ой строке матрицы смежности задает длину ребра, ведущего из \(i\)-й вершину в \(j\)-ую. Длины могут принимать любые значения от 0 до 1000000, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.
Выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.
| Ввод | Вывод |
|---|---|
3 1 2 0 -1 3 7 0 1 2 -1 0 |
-1 |