GESP 题解库 / 7 级题解 / [GESP202603 七级] 物流网络 · 第 1 / 24 题
GESP202603 七级 · P15803 · 困难

物流网络

枚举"被免单的那条边",再在 b 受限的子图上跑最短路。

🛣️
n, m ≤ 5000
城市数与公路数
💰
w, b ≤ 10⁹
费用 / 景观
⚡
O(m² log n)
枚举 + 最短路
🎯
枚举免单边 + Dijkstra
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

一个物流网络由 n 个城市和 m 条双向公路组成。每条公路有两个属性:运输费用 wᵢ、景观评分 bᵢ。

运输车从城市 1 运货到城市 n,需支付经过公路的费用之和。物流公司推出优惠:路径上景观评分最高的那条公路免单;若有多条公路景观评分同为最大值,则只免除其中一条的费用。

求从城市 1 到城市 n 的最小运输费用;若无法到达,输出 -1。

💡
人话翻译:一条路径的实际花费 = Σw − 被免边的那一份 w,而"被免的那条边"必须是这条路径上 b 最大的边。
所以不能简单地"免掉最贵的边"——如果最贵的边 b 不是最大,它就免不了。
正确姿势:枚举哪条边被免单,然后限制"只许走 b ⱼ ≤ bᵢ 的边"(这样 eᵢ 一定是路径上 b 最大的边,免它才合法),并把 eᵢ 的权改成 0,最后跑一次最短路。
把 m 条边都枚举一遍取最小值即可。

🔍 关键词提取

最短路径枚举关键边限制景观上限子图重建无解输出 −1

已知条件

项目说明
输入第一行 n、m;随后 m 行每行 u、v、w、b
输出最小费用;不可达输出 -1
数据范围1 ≤ n, m ≤ 5000
费用与景观1 ≤ w, b ≤ 10⁹
图的形态无向图,允许重边(平行边)
免单规则免掉路径上 b 最大的一条边;并列只免一条

需要解决的问题

02
思维导图
整理解题思路的全貌
🛣️ 枚举"谁被免单" + 限制 b ≤ bᵢ
🧠 问题转化
实际花费 = Σw − 被免边的 w
被免边必须是路径上 b 最大的边
"免掉最贵的边"是错的
需要"枚举 + 限制"才能刻画
🔁 枚举技巧
枚举第 i 条边作为被免边
重建子图:只留 b ⱼ ≤ bᵢ 的边
把第 i 条边的权改成 0
跑 Dijkstra 求 1 → n 的最短路
✅ 为什么正确
子图里 bᵢ 已是最大 → 免它合法
任何合法方案都能被某次枚举覆盖
取 m 次枚举的最小值 = 全局最优
任何一次都到不了则输出 −1
⚠️ 易错点
只免最贵的边(不看 b)
忘记限制 b ⱼ ≤ bᵢ
用 int 存距离(可达 5 × 10¹²)
多重边、并列最大的处理
03
样例手算推导
样例 1 与一个必须看懂的"陷阱"例子

🧮 样例 1:n = 3,三条公路

三条边: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)62–3(w=20)10 + 20 − 20 = 10
1 → 3(100, 1)11–3(w=100)100 − 100 = 0

最小花费 0 ✓

用"枚举免单边"跑一遍

1
免单边 = 1–2(w=10, b=5)

子图只允许 b ⱼ ≤ 5 的边:1–2 与 1–3(b=1)

1–2 的权改成 0,1–3 保持 100

1 → 3 的最短路:直接走 1–3,距离 100

本次结果 100

2
免单边 = 2–3(w=20, b=6)

子图允许 b ⱼ ≤ 6 的边:三条边全在

2–3 的权改成 0

1 → 3 的最短路:min(100, 10 + 0) = 10

本次结果 10

3
免单边 = 1–3(w=100, b=1)

子图只允许 b ⱼ ≤ 1 的边:只剩 1–3

1–3 的权改成 0

1 → 3 的最短路:0

本次结果 0

4
三次取最小

min(100, 10, 0) = 0

等价于"走 1–3,把它自己免掉"

✅ 答案 0

🔑
看清这里的因果关系:限制 b ⱼ ≤ bᵢ 的作用是"只许走景观不高于 eᵢ 的边",于是 eᵢ 在这条路径上必定是 b 最大的一条,免它完全合法。
而任何一组合法方案(选了某条 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错误
1
为什么"分层图免最贵边"会算出 5

这类写法只记"已经免过一次单"

于是它会贪心地把权最大的那条边免掉

得到 105 − 100 = 5

但那条边的 b = 1,根本不是路径上最大的

❌ 不符合题意

2
正确的枚举会怎么算

枚举免单边 = 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

⚠️
这是本题最容易踩的坑:很多人看到"免掉一条边的费用"就去建"0/1 分层图"(dist[结点][是否已免单]),那实际上算的是"免掉路径上最贵的边",与"免掉景观最高的边"完全不是一回事。
上面这个例子就是最直接的反驳:分层图得 5,正确答案是 100。
04
解法对比
枚举免单边 vs 无视景观的分层图 / 暴力枚举路径

⚔️ 解法对比

🟢 枚举免单边 + Dijkstra(推荐) 推荐

枚举哪条边被免单,限制 b ⱼ ≤ bᵢ,把该边权设为 0 后求最短路

  • 时间 O(m(m+n) log n)
  • m ≤ 5000 时约 3 × 10⁸
  • 代码约 50 行
  • 官方题解即此法
💡
正确性来源:限制 b ⱼ ≤ bᵢ 使被枚举的边必然是路径上 b 最大的边;反过来任意合法方案都能被对应的一次枚举覆盖。所以"取 m 次最小值"就是全局最优解。

🟠 分层图直接免最贵边

dist[u][0/1] 表示"还没免 / 已免一次"的最短路

  • 时间 O((n+m) log n) 很快
  • 但语义错了
  • 它免的是"最贵的边"
  • 样例能过,反例必挂
⚠️
它为什么会挂:题目免的是"b 最大"的边,而分层图免的是"w 最大"的边。
两者只有在"b 最大的边恰好也最贵"时才一致——这显然不是普遍情况(看上面的反例:算 5,正确 100)。

📈 性能对比

方案复杂度结论
枚举免单边 + DijkstraO(m(m+n) log n) ≈ 3 × 10⁸✅ 正确,官方做法
分层图(免最贵边)O((n+m) log n)❌ 语义错,反例即挂
暴力枚举所有简单路径指数级❌ 完全不可行
05
算法流程图
枚举 + Dijkstra 主流程
开始读入 n、m 与 m 条边 (u, v, w, b)ans = 无穷大枚举第 i 条边作为免单边(i = 1 … m)重建子图:只保留 b ⱼ ≤ bᵢ 的边,并把 eᵢ 的权改成 0在子图上跑 Dijkstra,求 1 → n 的最短路 dd < ans 吗?是 ✓ans = d否 ✗ans 不变m 条边都枚举完了吗?ans 仍为无穷大则输出 -1,否则输出 ans换下一条边
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🛣️ 最小费用计算器(枚举免单边)

第一行输入 n m,随后 m 行输入 u v w b。程序会逐条枚举"免单边",展示每次枚举的最短路与最终答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(枚举免单边 + Dijkstra)

#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 ⱼ ≤ bᵢ(子图放水,答案偏小);③ 距离用 int(5 × 10¹² 溢出);④ INF 设得太小(1e9 不够用,建议 4e18);⑤ 没处理平行边——本例用"存边数组 + 枚举下标"的写法天然支持重边,但如果把重边合并成一条会算错。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 3
1 2 10 5
2 3 20 6
1 3 100 1
0题面样例 1(免掉最贵的 100 得 0)
3 2
1 2 100 1
2 3 5 2
100反例:必须免"景观最高"的 5,而不是最贵的 100
2 1
1 2 5 7
0只有一条边,直接免掉
3 2
1 2 7 3
2 3 9 3
7景观并列最高,只免一条(免 9 留 7)
2 2
1 2 10 5
1 2 3 5
0平行边:任选一条免掉即可
3 1
1 2 5 7
-1到不了 n,输出 −1
✅
自查清单:① 是枚举免单边吗?② 限制了 b ⱼ ≤ bᵢ 吗?③ 被免边设为 0 权了吗?④ 用 long long 了吗?

🚨 易错点清单

⚠️
免错边:规则是免"b 最大"的边,不是"w 最大"的边。
⚠️
忘记限制 b ⱼ ≤ bᵢ:不限制就可能免掉一条"并非最大景观"的边,答案会偏小。
⚠️
用 int 存距离:最短路可达 5 × 10¹²,必须 long long。
⚠️
忽略不可达:所有枚举都到不了时要输出 -1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(m(m+n) log n)
空间复杂度
O(n + m)
枚举次数
m ≤ 5000
运算量
约 3 × 10⁸

时间怎么算的?

空间都用在哪?

每次 Dijkstra 需要一张邻接表 O(n + m) 与一个距离数组 O(n);边信息用 4 个长度为 m 的数组保存。

✅ 约 3 亿次基础操作,C++ 在 1 秒时限内可以跑完(官方题解就是这个复杂度)。关键是 m ≤ 5000 是小数据,枚举 + 单源最短路完全撑得住。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「枚举被特殊对待的那条边,再限制子图跑最短路」通用模板
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枚举全部失败则不可达所有最短路题的标准收尾
🌟
思考题:如果把规则改成"路径上景观最高的 k 条边都免单",枚举法还能用吗?(提示:可以,但要把"枚举一条边"升级成"枚举第 k 大的 b 值",子图限制改成 b ⱼ ≤ 第 k 大,并把"哪些边免费"绕一圈想清楚——把"枚举"从元素升级到阈值,是这类题常用的推广套路。)