简答题 偏难
#7159

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

交易市场

市场里面一共有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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;queue&gt; #include &lt;set&gt; #include &lt;vector&gt; #define INF 1000000000 using namespace std; struct exchangeTo {   int target;   int p;   exchangeTo(int a, int b) : target(a), p(b) {} }; struct path {   int pre;   int val; } dp[1005]; map&lt;int, vector&lt;exchangeTo&gt;&gt; tables; bool inPath(int n, int k) {   while (k != -1) {     if (n == k)       return true;     k = dp[k].pre;   }   return false; } int main() {   memset(dp, -1, sizeof(dp));   int n, m;   cin &gt;&gt; n &gt;&gt; m;   for (int i = 0; i &lt; m; i++) {     int x, y, z;     cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;     tables[x].push_back(exchangeTo(y, z));   }   dp[1].val = 0, dp[1].pre = 0;   bool done = false;   int result = 0;   queue&lt;int&gt; myqueues;   myqueues.push(1);   while (!myqueues.empty()) {     int top = myqueues.front();     myqueues.pop();     if (!tables[top].empty()) {       vector&lt;exchangeTo&gt;::iterator ii;       for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {         if (inPath(ii-&gt;target, top)) {           result = INF;           done = true;           break;         }         if (dp[top].val + ii-&gt;p &gt; dp[ii-&gt;target].val) {           dp[ii-&gt;target].val = dp[top].val + ii-&gt;p;           dp[ii-&gt;target].pre = top;           myqueues.push(ii-&gt;target); // 注意这里的更新         }         result = max(result, dp[ii-&gt;target].val);       }       if (done)         break;     }   }   cout &lt;&lt; result &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。