枚举"被免单的那条边",再在 b 受限的子图上跑最短路。
一个物流网络由 n 个城市和 m 条双向公路组成。每条公路有两个属性:运输费用 wᵢ、景观评分 bᵢ。
运输车从城市 1 运货到城市 n,需支付经过公路的费用之和。物流公司推出优惠:路径上景观评分最高的那条公路免单;若有多条公路景观评分同为最大值,则只免除其中一条的费用。
求从城市 1 到城市 n 的最小运输费用;若无法到达,输出 -1。
Σw − 被免边的那一份 w,而"被免的那条边"必须是这条路径上 b 最大的边。b ⱼ ≤ bᵢ 的边"(这样 eᵢ 一定是路径上 b 最大的边,免它才合法),并把 eᵢ 的权改成 0,最后跑一次最短路。最短路径枚举关键边限制景观上限子图重建无解输出 −1
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 m 行每行 u、v、w、b |
| 输出 | 最小费用;不可达输出 -1 |
| 数据范围 | 1 ≤ n, m ≤ 5000 |
| 费用与景观 | 1 ≤ w, b ≤ 10⁹ |
| 图的形态 | 无向图,允许重边(平行边) |
| 免单规则 | 免掉路径上 b 最大的一条边;并列只免一条 |
b ⱼ ≤ bᵢ?只有限制住上界,eᵢ 才一定是路径上 b 最大的边,免它才符合题意;否则 eᵢ 可能不是最大,这一次枚举就不合法eᵢ 的权设成 0 就等价于免单?因为我们只在"经过 eᵢ"这条路径上免它一份 w,把它当 0 权走,最短路自然不会再多付它的钱三条边:1–2 (w=10, b=5)、2–3 (w=20, b=6)、1–3 (w=100, b=1)。
| 路径 | 经过的边 (w, b) | 路径上最大 b | 被免的边 | 总花费 |
|---|---|---|---|---|
| 1 → 2 → 3 | (10, 5)、(20, 6) | 6 | 2–3(w=20) | 10 + 20 − 20 = 10 |
| 1 → 3 | (100, 1) | 1 | 1–3(w=100) | 100 − 100 = 0 |
最小花费 0 ✓
子图只允许 b ⱼ ≤ 5 的边:1–2 与 1–3(b=1)
1–2 的权改成 0,1–3 保持 100
1 → 3 的最短路:直接走 1–3,距离 100
本次结果 100
子图允许 b ⱼ ≤ 6 的边:三条边全在
2–3 的权改成 0
1 → 3 的最短路:min(100, 10 + 0) = 10
本次结果 10
子图只允许 b ⱼ ≤ 1 的边:只剩 1–3
1–3 的权改成 0
1 → 3 的最短路:0
本次结果 0
min(100, 10, 0) = 0
等价于"走 1–3,把它自己免掉"
✅ 答案 0
b ⱼ ≤ bᵢ 的作用是"只许走景观不高于 eᵢ 的边",于是 eᵢ 在这条路径上必定是 b 最大的一条,免它完全合法。把这个图当成一条"长廊":1 → 2 的边又贵又没景观(w=100, b=1),2 → 3 的边便宜但景观好(w=5, b=2)。整张图只有这一条从 1 到 n 的路径。
| 做法 | 免掉哪条边 | 总花费 | 是否正确 |
|---|---|---|---|
| 按题意(免 b 最大的边) | 2–3(b=2 最大,w=5) | 100 + 5 − 5 = 100 | 正确 |
| 错解:免最贵的边 | 1–2(w=100 最贵) | 100 + 5 − 100 = 5 | 错误 |
这类写法只记"已经免过一次单"
于是它会贪心地把权最大的那条边免掉
得到 105 − 100 = 5
但那条边的 b = 1,根本不是路径上最大的
❌ 不符合题意
枚举免单边 = 1–2(b=1):限制 b ⱼ ≤ 1,
边 2–3 的 b=2 > 1 被排除 → 到不了 3
枚举免单边 = 2–3(b=2):限制 b ⱼ ≤ 2 全部保留,
2–3 权改成 0 → 距离 100 + 0 = 100
✅ 答案 100
dist[结点][是否已免单]),那实际上算的是"免掉路径上最贵的边",与"免掉景观最高的边"完全不是一回事。枚举哪条边被免单,限制 b ⱼ ≤ bᵢ,把该边权设为 0 后求最短路
b ⱼ ≤ bᵢ 使被枚举的边必然是路径上 b 最大的边;反过来任意合法方案都能被对应的一次枚举覆盖。所以"取 m 次最小值"就是全局最优解。dist[u][0/1] 表示"还没免 / 已免一次"的最短路
| 方案 | 复杂度 | 结论 |
|---|---|---|
| 枚举免单边 + Dijkstra | O(m(m+n) log n) ≈ 3 × 10⁸ | ✅ 正确,官方做法 |
| 分层图(免最贵边) | O((n+m) log n) | ❌ 语义错,反例即挂 |
| 暴力枚举所有简单路径 | 指数级 | ❌ 完全不可行 |
第一行输入 n m,随后 m 行输入 u v w b。程序会逐条枚举"免单边",展示每次枚举的最短路与最终答案。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 4e18; int n, m; int U[5005], V[5005]; ll W[5005], B[5005]; // 第 freeId 条边被免单:只保留 b_j <= bLimit 的边,且第 freeId 条边权视为 0 ll dijkstra(int freeId, ll bLimit) { vector<vector<pair<int, ll> > > g(n + 1); for (int i = 0; i < m; i++) { if (B[i] > bLimit) continue; // 只能走景观不高于被免边的路 ll w = (i == freeId ? 0 : W[i]); // 被免边当 0 权 g[U[i]].push_back(make_pair(V[i], w)); g[V[i]].push_back(make_pair(U[i], w)); } vector<ll> dist(n + 1, INF); priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq; dist[1] = 0; pq.push(make_pair(0, 1)); while (!pq.empty()) { ll d = pq.top().first; int x = pq.top().second; pq.pop(); if (d > dist[x]) continue; for (int t = 0; t < (int)g[x].size(); t++) { int y = g[x][t].first; ll w = g[x][t].second; if (d + w < dist[y]) { dist[y] = d + w; pq.push(make_pair(dist[y], y)); } } } return dist[n]; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) scanf("%d %d %lld %lld", &U[i], &V[i], &W[i], &B[i]); ll ans = INF; for (int i = 0; i < m; i++) { // 枚举:第 i 条边被免单 ll d = dijkstra(i, B[i]); if (d < ans) ans = d; } if (ans >= INF) puts("-1"); // 任何枚举下都到不了 n else printf("%lld\n", ans); return 0; }
0,就等价于"走它不花钱";③ 距离必须用 long long——w 可达 10⁹、m 可达 5000,最短路最大约 5 × 10¹²,远超 int。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
if (B[i] > bLimit) continue; | 限制子图 | 保证 eᵢ 是路径上 b 最大的边 |
ll w = (i == freeId ? 0 : W[i]); | 免单 | 被免边当 0 权走 |
for (int i = 0; i < m; i++) | 枚举 | m 条边各当一次免单边 |
if (d < ans) ans = d; | 取最小 | 所有合法方案的最小值 |
if (ans >= INF) puts("-1"); | 无解判定 | 一次都没到达就输出 −1 |
b ⱼ ≤ bᵢ(子图放水,答案偏小);③ 距离用 int(5 × 10¹² 溢出);④ INF 设得太小(1e9 不够用,建议 4e18);⑤ 没处理平行边——本例用"存边数组 + 枚举下标"的写法天然支持重边,但如果把重边合并成一条会算错。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 3 | 0 | 题面样例 1(免掉最贵的 100 得 0) |
3 2 | 100 | 反例:必须免"景观最高"的 5,而不是最贵的 100 |
2 1 | 0 | 只有一条边,直接免掉 |
3 2 | 7 | 景观并列最高,只免一条(免 9 留 7) |
2 2 | 0 | 平行边:任选一条免掉即可 |
3 1 | -1 | 到不了 n,输出 −1 |
b ⱼ ≤ bᵢ 吗?③ 被免边设为 0 权了吗?④ 用 long long 了吗?-1。每次 Dijkstra 需要一张邻接表 O(n + m) 与一个距离数组 O(n);边信息用 4 个长度为 m 的数组保存。
✅ 约 3 亿次基础操作,C++ 在 1 秒时限内可以跑完(官方题解就是这个复杂度)。关键是 m ≤ 5000 是小数据,枚举 + 单源最短路完全撑得住。
// 「枚举被特殊对待的那条边,再限制子图跑最短路」通用模板 for (int i = 0; i < m; i++) { // 枚举"哪条边被特殊对待" // 1) 重建子图:只保留满足限制条件的边(本题:b_j <= B[i]) // 2) 把被选中的那条边的权改成 0(表示优惠/免单) // 3) 跑一次 Dijkstra(1 -> n),用结果更新答案 ans = min(ans, dist[n]); } // 为什么"限制子图"是必须的 // 不限制 -> 免掉的边可能不是路径上 b 最大的 -> 这次枚举不合法 // 限制了 -> 子图里 b_i 一定不小于其它边的 b -> 免它恰好符合题意 // 千万不要用"分层图免最贵边"代替 // dist[u][0/1] 那种写法免的是 max(w),而题目要的是 max(b) // 距离要用 long long:w ≤ 1e9、m ≤ 5000 -> 最短路可达 5e12 const ll INF = 4e18; // INF 也要跟着放大
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 枚举关键元素 | 把"路径上最大的那条边"枚举成已知量 | 图上"某条边被特殊处理"的最短路 |
| 限制子图 | 用 b ⱼ ≤ bᵢ 保证被枚举边就是最大 | 带阈值 / 前缀限制的图论问题 |
| 优惠设备份权 | 把选中边的权改成 0 表示免费 | 折扣、优惠券、免费通行类最短路 |
| 无解输出 −1 | 枚举全部失败则不可达 | 所有最短路题的标准收尾 |
b ⱼ ≤ 第 k 大,并把"哪些边免费"绕一圈想清楚——把"枚举"从元素升级到阈值,是这类题常用的推广套路。)