class Solution {
public:
vector<vector<pair<int, int>>> adj_list;
int cache[101][101];
//cache[node][count] : count 개 상태에서 해당 node에서 dst 노드까지의 거리

int dp(int dst, int k, int current_count, int current_node) {
if(current_node == dst) {
return 0;
}
if(current_count > k) {
return 1e7;
}
int & ret = cache[current_node][current_count];
if(ret == -1) {
int size = adj_list[current_node].size();
ret = 1e7;
for(int i = 0; i < size; i++) {
int next_node = adj_list[current_node][i].second;
int next_price = adj_list[current_node][i].first;
ret = min(ret, dp(dst, k, current_count + 1, next_node) + next_price);
}
}
return ret;
}
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
adj_list = vector<vector<pair<int,int>>>(n);
memset(cache, -1, sizeof cache);
for(auto& v: flights) {
adj_list[v[0]].push_back({v[2], v[1]});
}

int answer = dp(dst, k, 0, src);
if(answer >= 1e7) {
answer = -1;
}
return answer;
}
};