简答题
适中
#24831
物流网络
物流网络


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Highway {
int u, v;
int fee, b;
bool operator<(const Highway &other) const {
return b < other.b;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<Highway> highways(m);
for (int i = 0; i < m; i++) {
cin >> highways[i].u >> highways[i].v >> highways[i].fee >> highways[i].b;
}
sort(highways.begin(), highways.end());
vector<vector<pair<int, int>>> g(n + 1); // to, fee
vector<ll> dp1(n + 1, INF);
vector<ll> dpn(n + 1, INF);
dp1[1] = 0;
dpn[n] = 0;
ll answer = INF;
auto dijk = [&](int s, vector<ll>& dist) {
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
q.emplace(dist[s], s);
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (d > dist[u]) continue;
for (auto [v, w] : g[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
q.emplace(dist[v], v);
}
}
}
};
for (auto &r : highways) {
int u = r.u, v = r.v;
int w = r.fee, bb = r.b;
// 核心:这里 + bb!你原版漏掉了
if (dp1[u] != INF && dpn[v] != INF)
answer = min(answer, dp1[u] + dpn[v] + bb);
if (dp1[v] != INF && 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 << -1 << '\n';
else cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}</pre>
这道题暂未补解析。