物流网络 题解

题目分析

有一个包含 $n$ 个节点、$m$ 条边的无向图，每条边有费用 $w$ 和景观评分 $b$。我们需要从 $1$ 号节点走到 $n$ 号节点，并且可以免除路径上景观评分最高的那条边的费用（当多条边都是最高评分时，只免除其中一条）。目标是求出可能的最小花费；若无法到达则输出 -1。

数据范围：$n, m \le 5000$，$w, b \le 10^9$。本题对时间要求较高，朴素做法无法通过。

解题思路

直接枚举免费边再跑最短路，复杂度至少为 $O(m \cdot (n+m)\log n)$，在 $5000$ 的数据规模下会超时。我们需要更巧妙的方法。

观察“免除 $b$ 最大的一条边”这一条件：对于任意一条从 $1$ 到 $n$ 的路径，设其免费边为 $e$，则路径上其余所有边的 $b$ 值必然小于或等于 $e.b$。因此，我们可以考虑按照 $b$ 从小到大的顺序逐步将边加入图，那么在加入某条边 $e$ 时，当前图中所有边的 $b$ 都不超过 $e.b$。此时如果我们将 $e$ 当作免费边，路径的其余部分只能使用 $b \le e.b$ 的边（即当前图中的边）。这与我们在逐步加图的过程中直接求最短路的想法十分契合。

于是可以设计算法：按 $b$ 排序后依次加边，并用动态更新的最短路数组维护从 $1$ 和 $n$ 出发的最短距离，利用它们快速计算以当前边为免费边时的总费用。

算法说明

1. 数据结构

   • highways：存储所有边，按 $b$ 升序排序（$b$ 相同时按 $w$ 排序，其实顺序任意均可）。
   • dp1[i]：只使用当前已加入的边，从 $1$ 到 $i$ 的最短距离（不考虑免费）。
   • dpn[i]：只使用当前已加入的边，从 $i$ 到 $n$ 的最短距离（不考虑免费）。
   • network：邻接表，存储已加入的边的指针。
   • answer：全局最小费用，初始为正无穷。

2. 算法流程

   • 读入所有边并排序。
   • 初始化 dp1[1] = 0, dpn[n] = 0，其余为极大值。
   • 依次枚举每条边 r = (u, v, w, b)（按 $b$ 升序）：
     1. 尝试更新答案：假设我们免费边 r，路径为 1 → u (用已加入边) → v (免费) → ... → n 或其对称情况。总费用为
        dp1[u] + dpn[v] 和 dp1[v] + dpn[u]。用其中的较小值更新 answer。
        （注意此时的 dp 是在加入 r 之前的状态，包含了所有 $b$ 严格小于 $r.b$ 或同 $b$ 但已处理的边。）
     2. 将边 r 加入网络，并在 network 中为 u 和 v 添加这条边。
     3. 更新 dp1：从 u, v 出发，使用类似 SPFA 的松弛操作更新所有能从 1 以更短距离到达的点。
     4. 更新 dpn：同理，从 u, v 出发，松弛所有能更短到达 n 的点。
   • 所有边处理完后，若 answer 仍为极大值则输出 -1，否则输出 answer。

3. 为什么这样做是正确的？

   • 当我们决定将某条边 $r$ 作为免费边时，路径上其他边的 $b$ 必须 $\le r.b$。由于我们按 $b$ 升序加边，在考虑 $r$ 时，当前图中恰好包含了所有 $b \le r.b$ 的边（可能还不包括某些同 $b$ 的边，但它们后续会被加入，不影响已经用更小 $b$ 的边得到的最短路；而且对于同 $b$ 的多条边，后续处理会继续尝试更新答案，保证了最优解一定会被考虑到）。
   • 此时 dp1 和 dpn 表示只经过这些边的真实最短路，因此组合出的路径有效且费用正确。

4. 细节处理

   • 因为 $n,m$ 较小（$\le 5000$），在每次加入新边后，我们可以直接使用队列进行松弛，而不必每次重新跑完整的最短路。
   • 由于边权 $w$ 可能很大，距离数组需要使用 long long 类型，并初始化为一个足够大的值（如 $10^{18}$）。

时间复杂度分析

• 对边排序：$O(m \log m)$。
• 每条边加入时，会从它的两个端点开始松弛 dp1 和 dpn。每次更新只将距离确实变小的点入队，加上 $n,m \le 5000$，最坏情况下每条边都引起一次 $O(n+m)$ 的遍历，总体复杂度约为 $O(m(n+m))$。在本题数据范围下完全可以接受，运行时间远小于 1000ms。

C++ 参考代码

下面给出完整代码，并附有详细注释。

cpp
复制
1#include <algorithm>
2#include <iostream>
3#include <queue>
4#include <vector>
5using namespace std;
6
7struct Highway {
8    int u, v;
9    int fee, b;
10    // 按 b 升序排序
11    bool operator<(const Highway &other) const {
12        if (b != other.b) return b < other.b;
13        return fee < other.fee;
14    }
15};
16
17void solve() {
18    int n, m;
19    cin >> n >> m;
20    vector<Highway> highways(m);
21    for (int i = 0; i < m; ++i)
22        cin >> highways[i].u >> highways[i].v >> highways[i].fee >> highways[i].b;
23
24    sort(highways.begin(), highways.end());
25
26    // network[i] 存放与城市 i 相连的、已加入图的边的指针
27    vector<vector<const Highway *>> network(n + 1);
28    // dp1[k] = 从 1 到 k 只使用已加入边的最短距离
29    // dpn[k] = 从 k 到 n 只使用已加入边的最短距离
30    vector<long long> dp1(n + 1, (long long)1e18);
31    vector<long long> dpn(n + 1, (long long)1e18);
32    dp1[1] = 0;
33    dpn[n] = 0;
34
35    long long answer = (long long)1e18;
36
37    // 按 b 从小到大处理每一条公路
38    for (int ri = 0; ri < m; ++ri) {
39        const Highway &r = highways[ri];
40
41        // 尝试将当前公路作为免费公路，更新答案
42        // 路径：1 -> u (用 ≤r.b 的边) + 0 (免费) + v -> n (用 ≤r.b 的边)
43        answer = min(answer,
44                     min(dp1[r.u] + dpn[r.v],
45                         dp1[r.v] + dpn[r.u]));
46
47        // 将当前公路加入网络
48        network[r.u].push_back(&r);
49        network[r.v].push_back(&r);
50
51        // 更新 dp1（从 1 出发的最短路）
52        vector<int> cur;
53        cur.push_back(r.u);
54        cur.push_back(r.v);
55        for (int t = 0; t < (int)cur.size(); ++t) {
56            int i = cur[t];
57            for (const Highway *j : network[i]) {
58                int k = (i == j->u ? j->v : j->u);
59                if (dp1[i] + j->fee < dp1[k]) {
60                    dp1[k] = dp1[i] + j->fee;
61                    cur.push_back(k);   // 距离变小，需要继续松弛它的邻居
62                }
63            }
64        }
65
66        // 更新 dpn（到达 n 的最短路，方向与上述对称）
67        cur.clear();
68        cur.push_back(r.u);
69        cur.push_back(r.v);
70        for (int t = 0; t < (int)cur.size(); ++t) {
71            int i = cur[t];
72            for (const Highway *j : network[i]) {
73                int k = (i == j->u ? j->v : j->u);
74                if (dpn[i] + j->fee < dpn[k]) {
75                    dpn[k] = dpn[i] + j->fee;
76                    cur.push_back(k);
77                }
78            }
79        }
80    }
81
82    cout << (answer == (long long)1e18 ? -1 : answer) << '\n';
83}
84
85int main() {
86    ios::sync_with_stdio(false);
87    cin.tie(nullptr);
88    solve();
89    return 0;
90}

代码解释

• 结构体 Highway：存储公路的端点 u, v、费用 fee 和景观评分 b。重载 < 以按 b 升序排序。
• dp1 与 dpn：动态维护在当前已添加的边集合下，从城市 $1$ 到其他城市以及从其他城市到城市 $n$ 的最短路径长度。初始只有 $dp1[1]=0$ 和 $dpn[n]=0$，其余为 1e18 表示不可达。
• 主循环：
  1. 取出当前景观评分最小的边 r。
  2. 假设选择 r 作为被免除费用的那一条，则总费用为 min(dp1[r.u] + dpn[r.v], dp1[r.v] + dpn[r.u])，用其更新答案。
  3. 将该边加入 network。
  4. 用类似 SPFA 的方法，从新加入边的两端出发，向两个方向更新 dp1 和 dpn。这样能高效利用之前已算出的结果，避免每次重新跑完整的最短路。
• 最终输出：若 answer 仍为 1e18 说明没有合法路径，输出 -1；否则输出 answer。

通过上述方法，我们充分利用了“免除 $b$ 最高的边”这一条件的单调性，将问题转化为在逐渐扩展的图中维护双向最短路，最终在 $O(m(n+m))$ 的时间内得出答案。