BFS, C++


  • 0
    I
    class Solution {
    public:
        int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
            int res = 0;
            int N = flights.size();
            int K = days[0].size();
            vector<int> v(N,0), v_prev(N,0);
            unordered_set<int> r,r_prev;
            r.insert(0);
            r_prev = r;
            for(int i = 0; i < N; ++i)
               flights[i][i] = 1;
            for(int w = 0; w < K; ++w)
            {
                for(auto it = r_prev.begin(); it != r_prev.end(); ++it)
                {
                    for(int i = 0; i < N; ++i)
                    {
                        if(flights[*it][i])
                        {
                            v[i] = max(v[i],v_prev[*it]+days[i][w]);
                            res = max(res,v[i]);
                            r.insert(i);
                        }
                    }
                }
                v_prev = v;
                r_prev = r;
            }
            return res;
    
        }
    };
    

  • 0
    Z

    @i9r0k It seems a vector will be faster than unordered_set. The set will eventually near O(N) size.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.