C++ Solution | 100% | Knapsack DP Problem in Graph
we can assume it as a knapsack DP problem with passtime as cost[n], maxTime as Total Weight,edge time as weight[n]. we have to minimize the total cost with a We
we can assume it as a knapsack DP problem with passtime as cost[n], maxTime as Total Weight,edge time as weight[n]. we have to minimize the total cost with a Weight Constraints (maxTime).\nHere is the recursive approach with memoization.\n```\nclass Solution {\npublic:\n    int dp[1001][1001];\n    int solve(int time,vector<pair<int,int>> adj[],int v,vector<int> &pass){\n        if(time<0) return INT_MAX;\n        int n = pass.size();\n        if(v==n-1){\n            return pass[v];\n        }\n        if(dp[v][time]!=-1) return dp[v][time];\n        int cost = INT_MAX;\n        for(auto &x:adj[v]){\n            int u = x.first;\n            int temp = x.second;\n            if(temp<=time){\n               int sol = solve(time-temp,adj,u,pass);\n            cost = min(cost,sol);\n            }\n        }\n        if(cost==INT_MAX) return dp[v][time] = INT_MAX;\n        return dp[v][time] = cost + pass[v]; \n    }\n    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& pass) {\n        memset(dp,-1,sizeof(dp));\n        int n = pass.size();\n        vector<pair<int,int>> adj[n];\n        for(int i = 0;i<edges.size();i++){\n            adj[edges[i][0]].push_back(make_pair(edges[i][1],edges[i][2]));\n             adj[edges[i][1]].push_back(make_pair(edges[i][0],edges[i][2]));\n            \n        }\n        int ans = solve(maxTime,adj,0,pass);\n        if(ans==INT_MAX) return -1;\n        return ans;\n    }\n};\n```\nPlease leave a comment if needs help.\nIf you like it ...please upvote so that it can reach to other people also.
['Dynamic Programming', 'C++']