568

class Solution {
public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int n = flights.size(), k = days[0].size();
        vector<vector<int>> dp(n+1, vector<int>(k+1,0));
        vector<vector<int>> graph(n);
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(flights[i][j] || i == j)
                    graph[i].push_back(j);
            }
        }

        for(int week=k-1; week>=0; week--){
            for(int curCity=0; curCity<n; curCity++){
                for(int destCity: graph[curCity]){
                    dp[curCity][week] = max(days[destCity][week]+dp[destCity][week+1], dp[curCity][week]);
                }
            }
        }
        return dp[0][0];
    }
};