C++ Simple DFS + Memo (Knapsack) Solution
\nclass Solution {\npublic:\n    int dp[1001][1001],n;\n    int dfs(int curr,int k,vector<vector<pair<int,int>>>& g, vector<int>& cost){\n        if(curr==n-1) 
```\nclass Solution {\npublic:\n    int dp[1001][1001],n;\n    int dfs(int curr,int k,vector<vector<pair<int,int>>>& g, vector<int>& cost){\n        if(curr==n-1) // if destination reached, return it\'s cost\n            return cost[n-1];\n        if(dp[curr][k]!=-1)  // if already computed, return it\n            return dp[curr][k];\n        int mn=INT_MAX;\n        for(int i=0;i<g[curr].size();i++){\n            if(k<g[curr][i].second) // if time to visit the node, is less than remaining time, continue\n                continue;\n            int a=dfs(g[curr][i].first,k-g[curr][i].second,g,cost);\n            if(a!=INT_MAX)\n                mn=min(mn,cost[curr]+a);\n        }\n        return dp[curr][k]=mn;\n    }\n    int minCost(int k, vector<vector<int>>& edges, vector<int>& cost) {\n        n=cost.size();\n        int l=edges.size();\n        vector<vector<pair<int,int>>>g(n);\n        for(int i=0;i<l;i++){\n            g[edges[i][0]].push_back({edges[i][1],edges[i][2]});\n            g[edges[i][1]].push_back({edges[i][0],edges[i][2]});\n        }\n        memset(dp,-1,sizeof(dp));\n        dfs(0,k,g,cost); \n        return dp[0][k]==INT_MAX?-1:dp[0][k];\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'C']