| | | |
|
Форд-Беллман - 2
Алгоритм Форда-Беллмана
В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500\). Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.
Входные данные:
Программа получает на вход одно число n (2≤n≤13000).
Выходные данные:
Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном графе.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 |
117 |
| 2 |
3 |
-164 |
| |
![]()
|
|
Лабиринт знаний
Алгоритм Форда-Беллмана
В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход – в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.
Входные данные:
Первая строка входных данных содержит целые числа N (1 <= N <= 2000) – количество комнат и M (1 <= M <= 10000) – количество дверей. В каждой из следующих M строк содержится описание двери – номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.
Выходные данные:
Выведите ":)" – если можно получить неограниченно большой запас знаний, ":(" – если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 2
1 2 3
1 2 7
|
7 |
| |
![]()
|
|
Форд-Беллман
Алгоритм Форда-Беллмана
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
Входные данные
Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).
Выходные данные
Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |
| |
![]()
|
|
Беллман
Алгоритм Форда-Беллмана
Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).
Дана стартовая и конечная вершина, определить минимальное расстояние между ними.
Входные данные:
Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.
В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.
Выходные данные:
Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 2 1 4
1 2 100500
2 3 100500
|
Inf |
| |
![]()
|
|
Negcycle. Отрицательный цикл
Алгоритм Форда-Беллмана
Дан взвешенный ориентированный граф. Требуется определить, содержит ли он цикл отрицательного веса. Гарантируется, что все вершины графа достижимы из первой.
Входные данные:
Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно ( n ≤ 1 111, m ≤ 11 111).
Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя числами bi, ei и wi — номера концов ребра и его вес соответственно (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000). Обратите внимание, что в графе могут быть кратные ребра и петли.
Выходные данные:
Первая строка выходного файла должна содержать yes, если граф содержит цикл отрицательного веса и no — в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 4
2 1 -4
1 2 1
3 4 2
2 3 3 |
yes |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2 |
no |
| |
![]()
|
|
Форд-Беллман: Начало (C++)
Алгоритм Форда-Беллмана
Дополните программу, чтобы она верно решала следующую задачу.
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
Входные данные
Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).
Выходные данные
Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |
| |
![]()
|
|
Авиаперелеты
Алгоритм Форда-Беллмана
кратчайшие пути
Профессору Форду необходимо попасть на международную конференцию. Он хочет потратить на дорогу наименьшее количество денег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночевку в отелях), а днем будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелетов и составил набор подходящих авиарейсов, выяснив, что перелеты на выбранных направлениях совершаются каждую ночь и за одну ночь он не сможет совершить два перелета.
Теперь профессор хочет найти путь наименьшей стоимости, учитывая что до конференции осталось K ночей (то есть профессор может совершить не более K перелетов).
Входные данные
В первой строке находятся числа N (количество городов), M (количество авиарейсов), K (количество оставшихся ночей), S (номер города, в котором живет профессор), F (номер города, в котором проводится конференция).
Ограничения: 2≤N≤100, 1≤M≤105, 1≤K≤100, 1≤S≤N, 1≤F≤N.
Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит три натуральных числа: Si, Fi и Pi, где Si - номер города, из которого вылетает i-й рейс, Fi - номер го-рода, в который прилетает i-й рейс, Pi - стоимость перелета i-м рейсом. 1≤Si≤N, 1≤Fi≤N, 1≤Pi≤106.
Выходные данные
Выведите одно число - минимальную стоимость пути, подходящего для профессора. Если профессор не сможет за K ночей добраться до конференции, выведите число -1.
|
Ввод |
Вывод |
|
4 5 2 1 4
1 2 1
2 3 1
3 4 1
1 3 3
1 4 5
|
4 |
| |
![]()
|
|
Количество релаксаций
Алгоритм Форда-Беллмана
Дан взвешенный ориентированный граф. Необходимо найти минимальное количество фаз с релаксациями в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1.
Входные данные
Программа получает на вход одно число количество вершин n (2 ≤ n ≤ 100) и количество ребер m (2 ≤m ≤ 10 000). В следующих m строках вводятся три числа: a, b и c, где a и b – начало ребра и его конец, а c – вес ребра (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10 000).
Выходные данные
Программа должна вывести единственное целое число - минимальное количество релаксаций в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1.
|
Ввод |
Вывод |
|
4 3
1 2 1
2 3 1
3 4 1
|
1 |
|
4 3
2 3 1
1 2 1
1 3 4
|
2 |
(с) Шалдин В., 2017г.
| |
![]()
|