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;
}
};
댓글 영역
획득법
① NFT 발행
작성한 게시물을 NFT로 발행하면 일주일 동안 사용할 수 있습니다. (최초 1회)
② NFT 구매
다른 이용자의 NFT를 구매하면 한 달 동안 사용할 수 있습니다. (구매 시마다 갱신)
사용법
디시콘에서지갑연결시 바로 사용 가능합니다.