A20907. 物流网络
填空题
困难
知识点
题目描述
物流网络
题目描述
一个物流网络由n个城市和m条双向公路组成。每条公路都有两个属性:
- 运输费用wi
- 景观评分bi
当一辆运输车从城市1运送货物到城市n时，需要支付经过道路的运输费用之和。
为了推广旅游线路，物流公司推出了一项优惠政策:在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中一条的费用。
请你计算，从城市1到城市n的最小运输费用。
输入格式
第一行两个整数n,m，分别表示城市数量和公路数量。
接下来m行，每行四个整数u,v,w,b,表示存在一条连接城市u和城市v的双向公路，其中w为运输费用，b为景观评分。
输出格式
输出一个整数，表示从城市1到城市n的最小费用。
如果无法到达，输出-1。
样例
输入样例
3 3
1 2 10 5
2 3 20 6
1 3 100 1输出样例
0样例解释
路径1→2→3:费用10+20，最大美丽值6(边2-3)。免除20，总花费10。
路径1→3:费用100，最大美丽值1(边1-3)。免除100，总花费0。
最小费用为0。
数据范围
1≤n≤5000, 1≤m≤ 5000,1≤w,b≤109。
参考答案
参考程序1
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Highway {
int u, v;
int fee, b;
bool operator<(const Highway &other) const {
return b == other.b ? fee < other.fee : 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<const Highway *>> network(n + 1);
vector<long long> dp1(n + 1, (long long)1e18);
vector<long long> dpn(n + 1, (long long)1e18);
dp1[1] = 0, dpn[n] = 0;
long long answer = (long long)1e18;
for (int ri = 0; ri < m; ri++) {
const Highway &r = highways[ri];
answer = min(
answer,
min(dp1[r.u] + dpn[r.v],
dp1[r.v] + dpn[r.u])
);
network[r.u].push_back(&r);
network[r.v].push_back(&r);
vector<int> cur;
cur.push_back(r.u), cur.push_back(r.v);
for (int t = 0; t < cur.size(); t++) {
int i = cur[t];
for (int t2 = 0; t2 < network[i].size(); t2++) {
const Highway* j = network[i][t2];
int k = (i == j->u ? j->v : j->u);
if (dp1[i] + j->fee < dp1[k]) {
dp1[k] = dp1[i] + j->fee;
cur.push_back(k);
}
}
}
cur.clear();
cur.push_back(r.u), cur.push_back(r.v);
for (int t = 0; t < cur.size(); t++) {
int i = cur[t];
for (int t2 = 0; t2 < network[i].size(); t2++) {
const Highway* j = network[i][t2];
int k = (i == j->u ? j->v : j->u);
if (dpn[i] + j->fee < dpn[k]) {
dpn[k] = dpn[i] + j->fee;
cur.push_back(k);
}
}
}
cur.clear();
}
cout << (answer == (long long)1e18 ? -1 : answer) << '\n';
}
int main() {
solve();
return 0;
}
参考程序2
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Road {
int u, v, w, b;
bool operator<(const Road &other) const {
return b == other.b ? w < other.w : b < other.b;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<Road> roads(m);
for (auto &road : roads) {
cin >> road.u >> road.v >> road.w >> road.b;
}
sort(roads.begin(), roads.end());
vector<vector<const Road *>> graph(n + 1);
const auto relax = [&](sslocal://flow/file_open?url=vector%3Clong+long%3E+%26dist%2C+queue%3Cint%3E+%26q&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=) {
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto road : graph[u]) {
int v = u == road->u ? road->v : road->u;
if (dist[u] + road->w < dist[v]) {
dist[v] = dist[u] + road->w;
q.push(v);
}
}
}
};
vector<long long> dist1(n + 1, 1e18), distn(n + 1, 1e18);
dist1[1] = 0, distn[n] = 0;
queue<int> q1, qn;
long long ans = 1e18;
for (const auto &road : roads) {
ans = min(ans, min(dist1[road.u] + distn[road.v], dist1[road.v] + distn[road.u]));
graph[road.u].push_back(&road);
graph[road.v].push_back(&road);
q1.push(road.u);
q1.push(road.v);
relax(dist1, q1);
qn.push(road.u);
qn.push(road.v);
relax(distn, qn);
}
cout << (ans == 1e18 ? -1 : ans) << "\n";
}
int main() {
solve();
return 0;
}
上一题
下一题