首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7523

交易市场(2024-3-5级) 市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元…

交易市场(2024-3-5级)

市场里面一共有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">//参考代码1 #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><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;map&gt; #include &lt;set&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt; #include &lt;queue&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><p><br/></p>
这道题暂未补解析。