1.交易市场市场里面一共有n种物品，有m种交易途径，每个交易途径可以由(x,y,z)表示，意思

1.交易市场
市场里面一共有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

解析：

【喵呜刷题小喵解析】本题是一道典型的动态规划问题，可以使用拓扑排序+动态规划的方法解决。首先，我们需要建立一个邻接矩阵表示物品之间的交易关系，其中graph[i][j]表示第i种物品可以换取第j种物品并且得到多少收益。然后，我们还需要建立一个数组indeg，表示每个物品的入度，即有多少种物品可以交换得到该种物品。接下来，我们使用拓扑排序+动态规划的思想来解决问题。我们用一个队列q来保存待处理的物品，初始时只有第一种物品。然后，我们每次从队列中取出一个物品x，如果x等于n+1，说明已经处理完了所有物品，此时更新最大收益res。如果x的入度indeg[x]为0，说明x可以由其他物品交换得到，此时我们可以尝试用x交换得到其他物品，并将交换后的物品和当前收益加入队列。如果x的入度indeg[x]不为0，说明x不能直接交换得到，此时我们需要将x交换得到的每种物品和当前收益加入队列，并将这些物品的入度减1。最后，我们输出最大收益res，如果res为0，则输出1000000000表示可以赚取无穷多的收益。注意，由于题目中要求时间限制为1000，内存限制为65536，因此我们需要尽可能优化算法的时间复杂度和空间复杂度。在本题中，我们使用了拓扑排序+动态规划的方法，时间复杂度为O(nm)，空间复杂度为O(n^2)，满足题目要求。

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！