## Cheapest Flights Within K Stops | DFS + Pruning | Leetcode #787

This video explains a very important graph programming interview problem which is to find the minimum cost path from source to destination.This is a very typical shortest path problem and can be solved by using a variety of algorithms like Dijkstra, Floyd Warshall, Bellman Ford, BFS, DFS with memoization or pruning.In this question, we are allowed to have a maximum of K number of stops from source to destination.This is the only additional constraint.I have shown the simplest approach to solve this problem which is by using DFS + Pruning.I have first explained the intuition and then i have shown the working of the algorithm by taking an example.

```#define pb push_back
class Solution {
void solve(vector<vector<int>>& adj,vector<vector<int>>& cost,int src,int dst,int k,int& fare,int totCost,vector<bool>& visited)
{
if(k<-1)
return;
if(src==dst)
{
fare = min(fare,totCost);
return;
}

visited[src] = true;
{
}

visited[src] = false;
}
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

vector<vector<int>> cost(n+1,vector<int>(n+1));

for(int i=0;i<flights.size();++i)
{