1 Тема від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 475
    • Репутація: 84

Тема: Обхід графа з обмеженнями

Дано граф у форматі початкова вершина, кінцева вершина, вартість переходу.
Початок і кінець маршруту.
А також кількість зупинок, які можна зробити при переході
з початку до кінця вказаного маршруту.
Потрібно знайти найдешевший шлях з пункту А в пункт Б із обмеженою кількістю зупинок.
Моделюється найдешевший переліт літаком з обмеженою кількістю пересадок.
Завдання звідси https://leetcode.com/problems/cheapest- … scription/ .

Найдешевший маршрут я знаходжу ось так:

class Solution {
public:
    int findCheapestPrice(const int& n, const vector<vector<int>>& flights, const int& src, const int& dst, const int& k)
    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> dist_vert;
        vector<int> distances(n, 1e9 + 7);
        distances[src] = 0;
        dist_vert.push(make_pair(0, src));

        while (!dist_vert.empty()) {
            pair<int, int> item = dist_vert.top();
            int distance = item.first;
            int vertex = item.second;
            dist_vert.pop();
            for (size_t i = 0; i < flights.size(); ++i) {
                int source = flights[i][0];
                int destin = flights[i][1];
                int price = flights[i][2];
                if (source == vertex && (distance + price < distances[destin])) {
                    distances[destin] = distance + price;
                    dist_vert.push(make_pair(distances[destin], destin));
                }
            }
        }

        return distances[dst] >= 1e9 + 7 ? -1 : distances[dst];
    }
};

Але не розумію як реалізувати обмеження зупинок.
Має бути якийсь бектрекінґ абощо, проте фантазії на нього бракує.

2 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 475
    • Репутація: 84

Re: Обхід графа з обмеженнями

Ось так переписав. Код працює, але жере забагато пам'яті.

class Solution {
    bool visited(const int& vertex, const vector<int>& path)
    {
        for (size_t i = 0; i < path.size(); ++i) {
            if (path[i] == vertex) {
                return true;
            }
        }
        return false;
    }

public:
    int findCheapestPrice(const int& n, const vector<vector<int>>& flights, const int& src, const int& dst, const int& k)
    {
        queue<vector<int>> paths;
        vector<int> path;
        path.push_back(src);
        paths.push(path);
        vector<vector<int>> total_paths;
        int answer { INT_MAX };

        while (!paths.empty()) {
            path = paths.front();
            paths.pop();
            int last = path[path.size() - 1];
            if (last == dst) {
                int path_size = path.size();
                if (path_size <= k + 2) {

                    total_paths.push_back(path);
                }
            }
            for (size_t i = 0; i < flights.size(); ++i) {
                int source = flights[i][0];
                int target = flights[i][1];
                if (source == last && !visited(target, path)) {
                    vector<int> new_path(path);
                    new_path.push_back(target);
                    paths.push(new_path);
                }
            }
        }
        for (size_t i = 0; i < total_paths.size(); ++i) {
            int cur_path { 0 };
            for (size_t j = 0; j < total_paths[i].size() - 1; ++j) {
                for (size_t f = 0; f < flights.size(); ++f) {
                    if (flights[f][0] == total_paths[i][j] && flights[f][1] == total_paths[i][j + 1]) {
                        cur_path += flights[f][2];
                    }
                }
            }
            answer = min(cur_path, answer);
        }
        return total_paths.empty() ? -1 : answer;
    }
};