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;
}
};
BFS, C++


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