Алгоритм Форда-Беллмана

6 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Количество релаксаций#27274
Дан взвешенный ориентированный граф. Необходимо найти минимальное количество фаз с релаксациями в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 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г.

Алгоритм Форда-Беллмана
✓ 28✗ 35500лёгкаяВойти и решать
Форд-Беллман - 2#27271
В ориентированном взвешенном графе вершины пронумерованы числами от 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
Алгоритм Форда-Беллмана
✓ 42✗ 271700средняяВойти и решать
Форд-Беллман: Начало (C++)#27268
Дополните программу, чтобы она верно решала следующую задачу.

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
Требуется посчитать длины кратчайших путей от вершины номер 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 
Алгоритм Форда-Беллмана
✓ 81✗ 184500лёгкаяВойти и решать
Форд-Беллман#27267
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
 
Требуется посчитать длины кратчайших путей от вершины номер 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 
Алгоритм Форда-Беллмана
✓ 129✗ 84300лёгкаяВойти и решать
Беллман#21775
Дан ориентированный взвешенный граф с отрицательными ребрами (без отрицательных циклов).
Дана стартовая и конечная вершина, определить минимальное расстояние между ними.
 
Входные данные:
Дано 4 числа n, m, s, f - количество вершин, количество ребер, стартовая и конечная вершина(начиная с 1) соответственно.
В следующих m строках содержится по 3 числа - вершина 1, вершина 2 и цена перехода между вершинами.
 
Выходные данные:
Требуется вывести одно число - ответ на поставленную задачу. Если ответа нет - следует вывести Inf.
 
Примеры
№ Входные данные Выходные данные
1
4 2 1 4    
1 2 100500
2 3 100500
 Inf 
Алгоритм Форда-Беллмана
✓ 89✗ 137400лёгкаяВойти и решать
Negcycle. Отрицательный цикл#18440
Дан взвешенный ориентированный граф. Требуется определить, содержит ли он цикл отрицательного веса. Гарантируется, что все вершины графа достижимы из первой.


Входные данные: 
Первая строка входного файла содержит два натуральных числа 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
Алгоритм Форда-Беллмана
✓ 70✗ 190600лёгкаяВойти и решать
Поделиться
Класснуть