2 / 2 / 0
Регистрация: 27.02.2022
Сообщений: 18
|
||||||
1 | ||||||
Авиаперелеты. Алгоритм Форда Беллмана23.12.2022, 22:56. Показов 3318. Ответов 1
Метки нет (Все метки)
Профессору Форду необходимо попасть на международную конференцию. Он хочет потратить на дорогу наименьшее количество денег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночевку в отелях), а днем будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелетов и составил набор подходящих авиарейсов, выяснив, что перелеты на выбранных направлениях совершаются каждую ночь и за одну ночь он не сможет совершить два перелета.
Теперь профессор хочет найти путь наименьшей стоимости, учитывая что до конференции осталось 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 У меня есть проблема, мой код не правильно считает кол-ва ночей, затраченных на перелеты в сумме, и => неправильный ответ. Помогите пожалуйста найти ошибку)
0
|
23.12.2022, 22:56 | |
Ответы с готовыми решениями:
1
Алгоритм Форда-Беллмана Алгоритм Форда - Беллмана Алгоритм форда беллмана Алгоритм Беллмана-Форда |
2 / 2 / 0
Регистрация: 27.02.2022
Сообщений: 18
|
||||||
25.12.2022, 22:12 [ТС] | 2 | |||||
Все, проблема решена!
Вот код, если кому-то нужно:
0
|
25.12.2022, 22:12 | |
25.12.2022, 22:12 | |
Помогаю со студенческими работами здесь
2
Алгоритм Форда-Беллмана Как реализовать Алгоритм Беллмана-Форда со смежной матрицей? Матрица Форда Беллмана и метод Дейкстра Восстановление пути из алгоритма Форда-Беллмана Графы: реализация алгоритма Беллмана-Форда Реализация алгоритма Беллмана-Форда, с использование класса Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |