Re: [閒聊] 每日LeetCode

[wu10200512 (廷廷)]

※ 引述《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
推 JIWP: 大師