leetcode 787. Cheapest Flights Within K Stops K 站中转内最便宜的航班

Problem: 787. Cheapest Flights Within K Stops K 站中转内最便宜的航班

解题过程

广度优先搜索会超时，可能的情况太多了，而且不好剪枝的，不过用上记忆化搜索也是可以的

深度优先搜索 + 记忆化搜索，先用邻接表存一遍，然后分解成子问题，每次k-1，用哈希表记忆化搜索，拿到当前的最小值

Code

class Solution { public: int minmin = INT_MAX, destination, source; int ump[100000]; int dfs(vector<vector<pair<int, int>>>& array, int now, int k) { int key = (now * 100) + k; // if(ump.find(key)!=ump.end()) return ump[key]; if(ump[key] > 0) return ump[key]; int tmp, mi = INT_MAX; for(int j = 0; j < array[now].size(); j++) { if(array[now][j].first == destination) { mi = min(mi, array[now][j].second); } else if(array[now][j].first != source){ if(k==1) { continue; } tmp = dfs(array, array[now][j].first, k-1); if(tmp != INT_MAX) { tmp = tmp + array[now][j].second; } mi = min(mi, tmp); } } ump[key] = mi; return mi; } int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { destination = dst; source = src; // vector<vector<pair<char, short>>> array(n); vector<vector<pair<int, int>>> array(n); for(int i = 0; i < flights.size(); i++) { array[flights[i][0]].push_back( std::make_pair( flights[i][1], flights[i][2] ) ); } memset(ump, 0, sizeof(ump)); minmin = dfs(array, src, ++k); if(minmin==INT_MAX) return -1; return minmin; queue<pair<char, short>> qe; qe.push({src, 0}); int now, mincost = INT_MAX, cost; k++; while( !qe.empty() && k > 0) { int sz = qe.size(); k--; for(int i = 0; i < sz; i++) { now = qe.front().first; cost = qe.front().second; qe.pop(); for(int j = 0; j < array[now].size(); j++) { if(array[now][j].first == dst) { mincost = min(mincost, cost + array[now][j].second); } else if(array[now][j].first != now){ if(mincost > cost + array[now][j].second) { qe.push({array[now][j].first, cost + array[now][j].second}); } } } } } if(mincost==INT_MAX) return -1; return mincost; } };