题目背景
对应的选择、判断题：试题 - GESP 202603 C++ 七级 - 洛谷有题
题目描述
一个物流网络由 n 个城市和 m 条双向公路组成。每条公路都有两个属性：
- 运输费用 wi
- 景观评分 bi
当一辆运输车从城市 1 运送货物到城市 n 时，需要支付经过道路的运输费用之和。
为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中一条的费用。
请你计算，从城市 1 到城市 n 的最小运输费用。
输入格式
第一行两个整数 n,m，分别表示城市数量和公路数量。
接下来 m 行，每行四个整数 u,v,w,b，表示存在一条连接城市 u 和城市 v 的双向公路，其中 w 为运输费用，b 为景观评分。
输出格式
输出一个整数，表示从城市 1 到城市 n 的最小费用。
如果无法到达，输出-1。
输入输出样例
输入 #1复制
3 3 1 2 10 5 2 3 20 6 1 3 100 1
输出 #1复制
0
说明/提示
样例解释
路径 1→2→3：费用 10+20，最大美丽值 6（边 2−3）。免除 20，总花费 10。
路径 1→3：费用 100，最大美丽值 1（边 1−3）。免除 100，总花费 0。
数据范围
1≤n≤5000，1≤m≤5000，1≤w,b≤109。
代码实现：
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; typedef pair<ll,int> pli; const ll INF = 1e18; struct RawEdge{ int u,v; ll w,b; }; struct Edge{ int to; ll w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin >> n >> m; vector<RawEdge> es(m); for(int i=0;i<m;i++) { cin >> es[i].u >> es[i].v >> es[i].w >> es[i].b; } sort(es.begin(),es.end(),[](const RawEdge &a,const RawEdge &b){ return a.b < b.b; }); vector<vector<Edge>> g(n+1); ll ans = INF; vector<ll> dist1(n+1,INF), distn(n+1,INF); priority_queue<pli,vector<pli>,greater<pli>> q; auto dijk = [&](int s, vector<ll>&d) { fill(d.begin(),d.end(),INF); d[s]=0; q.push({0,s}); while(!q.empty()) { auto [dis,u]=q.top(); q.pop(); if(dis>d[u])continue; for(auto &e:g[u]) { int v=e.to; ll w=e.w; if(d[v]>d[u]+w) { d[v]=d[u]+w; q.push({d[v],v}); } } } }; int ptr=0; while(ptr<m) { int curB = es[ptr].b; int nxt=ptr; vector<RawEdge> batch; while(nxt<m && es[nxt].b == curB) { batch.push_back(es[nxt]); nxt++; } for(int i=ptr;i<nxt;i++) { int u=es[i].u,v=es[i].v; ll w=es[i].w; g[u].push_back({v,w}); g[v].push_back({u,w}); } ptr = nxt; dijk(1,dist1); dijk(n,distn); for(auto &e : batch) { int u=e.u, v=e.v; ll w=e.w; ll cost1 = dist1[u] + distn[v]; ll cost2 = dist1[v] + distn[u]; ll total = min(cost1,cost2); if(total < ans) ans = total; } } dijk(1,dist1); ans = min(ans, dist1[n]); if(ans >= INF) cout << -1 << endl; else cout << ans << endl; return 0; }
