交易市场 市场里面一共有n种物品，有m种交易途径，每个交易途径可以由(x,y,z)表示，意思是可以用第x种物品换成第y种物品，并且得到z元的收益（z均大于0）。最开始你只有第一种物品，请问最多可以赚取多少收益。 时间限制：1000 内存限制：65536 输入 第一行两个正整数n和m(n ≤ 1000，m ≤ 4000) 接下来m行，每行三个正整数x, y, z，意思是可以用第x种物品换成第y种物品，并且得到z元的收益。（1 ≤ x,y ≤ n, 1 ≤ z ≤ 100） 输出 一个整数表示最大收益，如果可以赚取无穷多的收益则输出1000000000 样例输入 3 3 1 2 2 2 3 3 1 3 4 样例输出 5

动态规划求解，时间复杂度O(nm)，空间复杂度O(n)。具体实现略。

本题是一个典型的动态规划问题。我们可以定义dp[i]为拥有第i种物品时的最大收益。由于每个交易途径可以由(x,y,z)表示，我们可以将问题转化为一个物品之间的转移问题。对于每个交易途径，我们可以选择保留当前物品继续获取收益，或者选择交换物品以获取更大的收益。因此，我们可以使用动态规划来求解这个问题。状态转移方程为：dp[i] = max(dp[i], dp[x] + z)，其中(x,y,z)表示一个交易途径。最终答案为dp[n]，即拥有第n种物品时的最大收益。由于题目中有内存限制，我们需要优化算法的空间复杂度，可以使用滚动数组等方法来减少空间消耗。时间复杂度为O(nm)，空间复杂度为O(n)。