100 #3951. 交易市场

交易市场

描述

市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元的收益(z均大于0)。最开始你只有第一种物品,请问最多可以赚取多少收益。

输入

第一行两个正整数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

解法

这道题用动态规划可以做。采用我为人人型递推。

dp[i]表示最后是第i种物品时的最大价值,无穷多的收益等于出现环,要判断环所以要记录路径。扫描到每个转换关系时更新目标节点的dp。

注意这道题还有广搜的思想,动态规划的节点顺序是用队列来决定,有的节点根本到不了就不用考虑它的转换关系。有的节点增加了转换关系就应该重新计算。

Limitation

1s, 1024KiB for each test case.