Авиаперелеты. Алгоритм Форда Беллмана

@Oleg_Rodin · Регистрация: 27.02.2022

Author24 — интернет-сервис помощи студентам

Профессору Форду необходимо попасть на международную конференцию. Он хочет потратить на дорогу наименьшее количество денег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночевку в отелях), а днем будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелетов и составил набор подходящих авиарейсов, выяснив, что перелеты на выбранных направлениях совершаются каждую ночь и за одну ночь он не сможет совершить два перелета.

Теперь профессор хочет найти путь наименьшей стоимости, учитывая что до конференции осталось 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

У меня есть проблема, мой код не правильно считает кол-ва ночей, затраченных на перелеты в сумме, и => неправильный ответ. Помогите пожалуйста найти ошибку)

C++

#include <iostream>
#include <vector>
#include <climits>
 
#define INF INT_MAX
 
struct Flight{
    int first, second, cost;
};
 
int num_of_cities, num_of_flights, max_nights, start, finish;
std::vector<Flight> e;
 
void FordBellman() {
    std::vector<int> dist(num_of_cities, INF);
    dist[start - 1] = 0;
    int nights;
    for (;;) {
        nights = 0;
        bool was_relaxed = false;
        for (int i = 0; i < num_of_flights; ++i) {
            if (e[i].first != INF) {
                if (dist[e[i].second] > dist[e[i].first] + e[i].cost) {
                    dist[e[i].second] = dist[e[i].first] + e[i].cost;
                    was_relaxed = true;
                    ++nights;
                }
            }
        }
        if (!was_relaxed) {
            break;
        }
    }
 
    if (nights <= max_nights) {
        std::cout << dist[finish - 1];
    }
    else {
        std::cout << -1;
    }
}
 
int main() {
    std::cin >> num_of_cities >> num_of_flights >> max_nights >> start >> finish;
    Flight t{};
    for (int i = 0; i < num_of_flights; ++i) {
        std::cin >> t.first >> t.second >> t.cost;
        --t.first, --t.second;
 
        e.push_back(t);
    }
 
    FordBellman();
 
    std::cout << std::endl;
    return 0;
}

Если что, ссылка на задачу: https://informatics.msk.ru/mod... rid=1995#1

@Oleg_Rodin · 25.12.2022, 22:12 **[ТС]**

Все, проблема решена!

Вот код, если кому-то нужно:

C++

#include <iostream>
#include <vector>
#include <tuple>
#include <climits>
 
#define INF INT_MAX
 
int main() {
    int num_of_cities, num_of_flights, max_nights, start, finish;
    std::cin >> num_of_cities >> num_of_flights >> max_nights >> start >> finish;
    std::vector<std::tuple<int, int, int>> all_flights;
    for (int i = 0; i < num_of_flights; ++i) {
        int first, second, cost;
        std::cin >> first >> second >> cost;
        all_flights.emplace_back(first - 1, second - 1, cost);
    }
 
    std::vector<std::vector<int>> dist(max_nights + 1);
    for (int night = 0; night < max_nights + 1; ++night) {
        for (int city = 0; city < num_of_cities; ++city) {
            if (night == 0 && city == start - 1) {
                dist[night].push_back(0);
            }
            else {
                dist[night].push_back(INF);
            }
        }
    }
 
    for (;;) {
        bool was_relaxed = false;
        for (int night = 1; night < max_nights + 1; ++night) {
            for (auto & flight : all_flights) {
                int u, v, w;
                std::tie(u, v, w) = flight;
                if (dist[night - 1][u] != INF) {
                    if (dist[night][v] > dist[night - 1][u] + w) {
                        dist[night][v] = dist[night - 1][u] + w;
                        was_relaxed = true;
                    }
                }
            }
        }
        if (!was_relaxed) {
            break;
        }
    }
 
    int min_cost = INF;
    for (int night = 0; night <= max_nights; night++) {
        if (dist[night][finish - 1] < min_cost) {
            min_cost = dist[night][finish - 1];
        }
    }
 
    if (min_cost == INF) {
        std::cout << -1;
    }
    else {
        std::cout << min_cost;
    }
    std::cout << std::endl;
    return 0;
}

	25.12.2022, 22:12

Опции темы