# Leetcode 803 Solution

https://leetcode.com/problems/cheapest-flights-within-k-stops

## Solution

``````class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
vector<vector<pair<int, int>>> edges(n);
for (const auto& flight: flights)
edges[flight[0]].push_back(make_pair(flight[1], flight[2]));

vector<int> costs(n, INT_MAX);
costs[src] = 0;

queue<tuple<int, int, int>> q;
q.push(make_tuple(src, 0, 0));

unordered_map<int, pair<int, int>> s;
s[0] = make_pair(0, 0);
for (int i = 0; i < n; i++)
s[i] = make_pair(INT_MAX, INT_MAX);

while (q.empty() == false)
{
auto t = q.front();
q.pop();
auto i = std::get<0>(t);
auto cost = std::get<1>(t);
auto stop = std::get<2>(t);

costs[i] = min(costs[i], cost);

if (stop > K)
continue;

for (auto& neigh: edges[i])
{
int j = neigh.first;
int target_cost = neigh.second + cost;
int target_stop = stop + 1;

if (s.find(j) == s.end() ||
!(s[j].first < target_cost && s[j].second < target_stop))
{
q.push(make_tuple(neigh.first, target_cost, target_stop));
s[j] = make_pair(
min(s[j].first, target_cost),
min(s[j].second, target_stop)
);
}
}
}

return costs[dst] == INT_MAX ? -1 : costs[dst];
}
};
``````