简答题 适中
#24831

物流网络

物流网络

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;vector&gt; using namespace std; typedef long long ll; const ll INF = 1e18; struct Highway {   int u, v;   int fee, b;   bool operator&lt;(const Highway &amp;other) const {     return b &lt; other.b;   } }; void solve() {   int n, m;   cin &gt;&gt; n &gt;&gt; m;   vector&lt;Highway&gt; highways(m);   for (int i = 0; i &lt; m; i++) {     cin &gt;&gt; highways[i].u &gt;&gt; highways[i].v &gt;&gt; highways[i].fee &gt;&gt; highways[i].b;   }   sort(highways.begin(), highways.end());   vector&lt;vector&lt;pair&lt;int, int&gt;&gt;&gt; g(n + 1); // to, fee   vector&lt;ll&gt; dp1(n + 1, INF);   vector&lt;ll&gt; dpn(n + 1, INF);   dp1[1] = 0;   dpn[n] = 0;   ll answer = INF;   auto dijk = [&amp;](int s, vector&lt;ll&gt;&amp; dist) {     priority_queue&lt;pair&lt;ll, int&gt;, vector&lt;pair&lt;ll, int&gt;&gt;, greater&lt;&gt;&gt; q;     q.emplace(dist[s], s);     while (!q.empty()) {       auto [d, u] = q.top();       q.pop();       if (d &gt; dist[u]) continue;       for (auto [v, w] : g[u]) {         if (dist[v] &gt; d + w) {           dist[v] = d + w;           q.emplace(dist[v], v);         }       }     }   };   for (auto &amp;r : highways) {     int u = r.u, v = r.v;     int w = r.fee, bb = r.b;     // 核心:这里 + bb!你原版漏掉了     if (dp1[u] != INF &amp;&amp; dpn[v] != INF)       answer = min(answer, dp1[u] + dpn[v] + bb);     if (dp1[v] != INF &amp;&amp; dpn[u] != INF)       answer = min(answer, dp1[v] + dpn[u] + bb);     // 再加边进图     g[u].emplace_back(v, w);     g[v].emplace_back(u, w);     // 重新跑Dijkstra更新最短路     dijk(1, dp1);     dijk(n, dpn);   }   if (answer == INF) cout &lt;&lt; -1 &lt;&lt; '\n';   else cout &lt;&lt; answer &lt;&lt; '\n'; } int main() {   ios::sync_with_stdio(false);   cin.tie(nullptr);   solve();   return 0; }</pre>
这道题暂未补解析。