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

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

#include<tuple>
typedef std::tuple<int,int,int> ti;
class Solution{
public:
    int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int K) {
        std::vector<std::vector<std::pair<int,int>>>vp(n);
        for(const auto&f:flights)   vp[f[0]].emplace_back(f[1],f[2]);
        std::priority_queue<ti,std::vector<ti>,std::greater<ti>>pq;
        pq.emplace(0,src,K+1);
        while(!pq.empty()){
           // auto [cost,u,stops] = pq.top();//replaced for C++11 as
            auto cost=std::get<0, int>(pq.top());
            auto u=std::get<1, int>(pq.top());
            auto stops=std::get<2, int>(pq.top());

            pq.pop();
            if(u==dst)  return cost;
            if(!stops)  continue;
            for(auto to:vp[u]){
                //auto [v,w] = to;//replaced for C++11 as
                auto v=std::get<0, int>(to);
                auto w=std::get<1, int>(to);
                pq.emplace(cost+w,v,stops-1);
            }
        }
        return -1;
    }
};

int flights_number=4, start=1, finish=5, stops_max=2;
using vec_int=std::vector;
using vec_source = std::vector<vec_int>;
vec_source flights=
{//from, to, price
{1, 2, 100 }, {1, 3, 200}, {1, 5, 5}, {2, 3, 5},
{2, 5, 50}, {2, 6, 30}, {3, 5, 2}, {5, 6, 10}, {5, 1, 1000}
};
//the sample of call:
int res=Solution{}.findCheapestPrice(flights_number, flights, start, finish, stops_max);