— For the DP table.
Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maximumWeightedKEdgePath(int n, vector<vector<int>>& edges, int k, int t) {\n        vector<vector<pair<int,int>>> g(n);\n        vector<int> indeg(n);\n        for (auto& e : edges) {\n            g[e[0]].emplace_back(e[1], e[2]);\n            indeg[e[1]]++;\n        }\n        vector<vector<int>> dp(n, vector<int>(k+1, -1));\n        for (int i = 0; i < n; ++i) dp[i][0] = 0;\n        queue<int> q;\n        for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);\n        while (!q.empty()) {\n            int u = q.front(); q.pop();\n            for (auto& [v, w] : g[u]) {\n                for (int e = 0; e < k; ++e) {\n                    if (dp[u][e] != -1 && dp[u][e] + w < t) {\n                        dp[v][e+1] = max(dp[v][e+1], dp[u][e] + w);\n                    }\n                }\n                if (--indeg[v] == 0) q.push(v);\n            }\n        }\n        int ans = -1;\n        for (int i = 0; i < n; ++i) ans = max(ans, dp[i][k]);\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maximumWeightedKEdgePath</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> edges</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> k</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> t</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">pair</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">,</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int>>></span><span style=\"color:#6F42C1;--shiki-d
Related Tags
