class Solution {
public:
    int findCheapestPrice(const int& n, const vector<vector<int>>& flights, const int& src, const int& dst, const int& k)
    {
        vector<vector<pair<int, int>>> graph(n);
        for (const auto& item : flights) {
            graph[item[0]].push_back({ item[1], item[2] });
        }
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> vertexes;
        vertexes.push({ 0, src, 0 });
        vector<int> dist(n + 1, INT_MAX);

        while (!vertexes.empty()) {
            auto item = vertexes.top();
            vertexes.pop();
            int price = item[0];
            int vertex = item[1];
            int end = item[2];

            if (vertex == dst) {
                return price;
            }
            if (dist[vertex] < end) {
                continue;
            }
            dist[vertex] = end;

            if (end > k) {
                continue;
            }
            for (const auto& next_vertex : graph[vertex]) {
                vertexes.push({ price + next_vertex.second, next_vertex.first, end + 1 });
            }
        }
        return -1;
    }
};

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;
    }
};