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