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

旅游规划 有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短…

旅游规划

有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。

时间限制:1000

内存限制:65536

输入

输入说明:输入数据的第 1 行给出 4 个正整数 n、m、s、d,其中 n(2 ≤ n ≤ 500)是城市的个数,顺便假设城市的编号为 0~(n-1);m 是高速公路的条数;s 是出发地的城市编号;d 是目的地的城市编号。随后的 m 行中,每行给出一条高速公路的信息,分别是:城市 1、城市 2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过 500。输入保证解的存在。

输出

在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。


样例输入

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

样例输出

3 40
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;bits/stdc++.h&gt; using namespace std;   struct Edge { int to, dist, cost; };   int main() {     int n, m, s, d; cin &gt;&gt; n &gt;&gt; m &gt;&gt; s &gt;&gt; d;     vector&lt;vector&lt;Edge&gt;&gt; g(n);     for (int i = 0, a, b, c, f; i &lt; m; ++i) {         cin &gt;&gt; a &gt;&gt; b &gt;&gt; c &gt;&gt; f;         g[a].push_back({b, c, f});         g[b].push_back({a, c, f});     }     vector&lt;int&gt; dist(n, INT_MAX), fee(n, INT_MAX);     priority_queue&lt;tuple&lt;int, int, int&gt;, vector&lt;tuple&lt;int, int, int&gt;&gt;, greater&lt;&gt;&gt; pq;     dist[s] = 0, fee[s] = 0; pq.emplace(0,  0, s);     while (!pq.empty())  {         auto [d, f, u] = pq.top();  pq.pop();          if (d &gt; dist[u] || (d == dist[u] &amp;&amp; f &gt; fee[u])) continue;         for (auto &amp;[v, dd, ff] : g[u]) {             if (d + dd &lt; dist[v] || (d + dd == dist[v] &amp;&amp; f + ff &lt; fee[v])) {                 dist[v] = d + dd, fee[v] = f + ff;                 pq.emplace(dist[v],  fee[v], v);             }         }     }     cout &lt;&lt; dist[d] &lt;&lt; " " &lt;&lt; fee[d]; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;queue&gt; using namespace std; const int INF = 1e9; struct Edge { int to, len, cost; }; int main() { int n, m, s, d; cin &gt;&gt; n &gt;&gt; m &gt;&gt; s &gt;&gt; d; vector&lt;vector&lt;Edge&gt;&gt; graph(n); for (int i = 0; i &lt; m; ++i) { int u, v, len, c; cin &gt;&gt; u &gt;&gt; v &gt;&gt; len &gt;&gt; c; graph[u].push_back({v, len, c}); graph[v].push_back({u, len, c}); } vector&lt;int&gt; dist(n, INF); vector&lt;int&gt; cost(n, INF); dist[s] = 0; cost[s] = 0; using pii = pair&lt;int, int&gt;; priority_queue&lt;pii, vector&lt;pii&gt;, greater&lt;pii&gt;&gt; pq; pq.push({0, s}); while (!pq.empty()) { auto [cur_dist, u] = pq.top(); pq.pop(); if (cur_dist &gt; dist[u]) continue; for (auto &amp;edge : graph[u]) { int v = edge.to; int new_dist = cur_dist + edge.len; int new_cost = cost[u] + edge.cost; if (new_dist &lt; dist[v] || (new_dist == dist[v] &amp;&amp; new_cost &lt; cost[v])) { if (new_dist &lt; dist[v]) { dist[v] = new_dist; cost[v] = new_cost; } else { cost[v] = new_cost; } pq.push({new_dist, v}); } } } cout &lt;&lt; dist[d] &lt;&lt; " " &lt;&lt; cost[d] &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。