Re: [閒聊] 每日LeetCode已回收
※ 引述《wu10200512 (廷廷)》之銘言：
: 我她媽就用了一個map一個queue
: 記憶體就爆了
: 他這限制也抓太緊
: 操機掰哩 還medium
: 改一個小時還是改不出來
: 明天再看看
: ==
: 787. Cheapest Flights Within K Stops
: class Solution {
: public:
: int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int
: dst, int k) {
: unordered_map<int, vector<pair<int, int>>> mp;
: for(auto& f:flights){
: mp[f[0]].push_back({f[1],f[2]});
: }
: int ans=INT_MAX;
: queue<pair<int, int>> q;
: q.push({src,0});
: while(!q.empty() && k-->=0){
: int n=q.size();
: for(int i=0; i<n; i++){
: auto temp=q.front();
: q.pop();
: for(auto& v:mp[temp.first]){
: if(ans<=temp.second+v.second) continue;
: if(v.first==dst) {
: ans=min(ans, temp.second+v.second);
: continue;
: }
: q.push({v.first, temp.second+v.second});
: }
: }
: }
: if(ans==INT_MAX) return -1;
: return ans;
: }
: };
多用一個mp做dp
這樣記憶體就不會爆了
這不算hard太狠了
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int
dst, int k) {
unordered_map<int, vector<pair<int, int>>> mp;
for(auto& f:flights){
mp[f[0]].push_back({f[1],f[2]});
}
queue<pair<int, int>> q;
q.push({src,0});
unordered_map<int, int> tempMin;
tempMin[src]=0;
while(!q.empty() && k-->=0){
int n=q.size();
for(int i=0; i<n; i++){
auto temp=q.front();
q.pop();
for(auto& v:mp[temp.first]){
if(tempMin.count(v.first) && tempMin[v.first]<=temp.second
+v.second){
continue;
}
else{
tempMin[v.first]=temp.second+v.second;
}
q.push({v.first, temp.second+v.second});
}
}
}
if(!tempMin.count(dst)) return -1;
return tempMin[dst];
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.149.184 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708765254.A.829.html
推
02/24 17:02,
1年前
, 1F
02/24 17:02, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 713 之 719 篇)：