-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathCheapest-flights-within-k-steps
42 lines (41 loc) · 1.08 KB
/
Cheapest-flights-within-k-steps
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
unordered_map<int,int>vis;
unordered_map<int,vector<pair<int,int>>>adj;
void dfs(int src,int des,int k,int &ans,int temp)
{
if(k<-1)
return;
if(src==des)
{
ans=min(temp,ans);
cout<<"ans"<<ans<<endl;
return;
}
vis[src]=1;
for(auto itr:adj[src])
{
if(vis[itr.first]!=1&&ans>=temp+itr.second)
{
cout<<itr.first<<" "<<temp+itr.second<<endl;
dfs(itr.first,des,k-1,ans,temp+itr.second);
}
}
vis[src]=0;
}
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);
for(int i=0;i<flights.size();i++)
{
adj[flights[i][0]].push_back({flights[i][1],flights[i][2]});
}
int ans=INT_MAX;
int temp=0;
dfs(src,dst,k,ans,temp);
if(ans==INT_MAX)
return -1;
return ans;
}
};