题目理解

我们有一个有向图，包含 $N$ 个城市和 $M$ 条有向道路，每条道路有长度 $L_i$ 和关闭费用 $C_i$。
给定起点 $A$ 和终点 $B$，国王希望关闭所有出现在从 $A$ 到 $B$ 且总长度不超过 $D$ 的路径上的道路。
对于多个询问 $D_1, D_2, \dots, D_Q$，需要分别计算关闭这些道路的最小总费用。

问题转化

设一条路径 $P$ 包含若干条边 $e_1, e_2, \dots, e_k$，路径总长度 $len(P) = \sum L_{e_i}$。
对于给定的 $D$，需要关闭所有满足以下条件的边 $e$：
存在一条从 $A$ 到 $B$ 的路径 $P$ 包含 $e$，且 $len(P) \le D$。

关键观察

对于一条边 $(u, v, L, C)$，它出现在某条从 $A$ 到 $B$ 且长度不超过 $D$ 的路径上，当且仅当： [ dist(A, u) + L + dist(v, B) \le D ] 其中 $dist(A, u)$ 表示从 $A$ 到 $u$ 的最短距离，$dist(v, B)$ 表示从 $v$ 到 $B$ 的最短距离。

算法步骤

1. 计算最短路径

• 从 $A$ 出发，在原图上跑 Dijkstra，得到 $dist_A[u]$（从 $A$ 到 $u$ 的最短距离）。
• 从 $B$ 出发，在反图上跑 Dijkstra，得到 $dist_B[v]$（从 $v$ 到 $B$ 的最短距离）。

2. 计算每条边的关键值

对于边 $i = (u, v, L, C)$，计算： [ key_i = dist_A[u] + L + dist_B[v] ] 这表示经过该边的最短可能路径长度。

3. 预处理前缀和

• 将所有边按 $key_i$ 从小到大排序。
• 计算关闭费用的前缀和数组 $prefix[k] = \sum_{j=1}^k C_{i_j}$。

4. 回答询问

对于每个询问 $D$，在排序后的边数组中二分查找最大的 $k$ 使得 $key_{i_k} \le D$，答案即为 $prefix[k]$。

代码实现解析

1. 数据结构

struct node {
    long long s, e, z, t;  // 起点, 终点, 长度, 关闭费
} ak[200010];
struct abo {
    long long g, h;  // key值, 关闭费
} jg[200010];
struct nd {
    vector<long long> w, nxt;  // 邻接表存储
    long long dist;
} g[200010];

2. Dijkstra 算法

void dijkstra(int s) {
    // 初始化距离为无穷大
    for (int i = 1; i <= n; ++i)
        g[i].dist = 4e9;
    
    g[s].dist = 0;
    priority_queue<pq, vector<pq>, greater<pq>> q;
    q.push({s, 0});
    
    while (!q.empty()) {
        // 取出当前距离最小的节点
        pq c = q.top();
        q.pop();
        
        if (c.dist != g[c.x].dist) continue;
        
        // 松弛相邻节点
        for (int i = 0; i < g[c.x].nxt.size(); i++) {
            int neighbor = g[c.x].nxt[i];
            long long new_dist = c.dist + g[c.x].w[i];
            if (new_dist < g[neighbor].dist) {
                g[neighbor].dist = new_dist;
                q.push({neighbor, new_dist});
            }
        }
    }
}

3. 主流程

int main() {
    // 读入数据
    scanf("%lld%lld%lld%lld", &n, &m, &a, &b);
    
    // 建原图
    for (long long i = 1; i <= m; i++) {
        scanf("%lld%lld%lld%lld", &l1, &l2, &l3, &l4);
        g[l1].nxt.push_back(l2);
        g[l1].w.push_back(l3);
        ak[i] = {l1, l2, l3, l4};
    }
    
    // 计算从A出发的最短距离
    dijkstra(a);
    for (int i = 1; i <= n; i++) 
        mn[i] = g[i].dist;
    
    // 清空图，建反图
    for (int i = 1; i <= n; i++) {
        g[i].w.clear();
        g[i].nxt.clear();
    }
    for (int i = 1; i <= m; i++) {
        g[ak[i].e].nxt.push_back(ak[i].s);
        g[ak[i].e].w.push_back(ak[i].z);
    }
    
    // 计算到B的最短距离（在反图上）
    dijkstra(b);
    
    // 计算每条边的key值
    for (long long i = 1; i <= m; i++)
        jg[i] = {mn[ak[i].s] + ak[i].z + g[ak[i].e].dist, ak[i].t};
    
    // 排序并计算前缀和
    sort(jg + 1, jg + m + 1, cmp);
    for (long long i = 1; i <= m; i++)
        ans[i] = ans[i - 1] + jg[i].h;
    
    // 处理询问
    scanf("%lld", &qq);
    for (long long i = 1; i <= qq; i++) {
        scanf("%lld", &l1);
        // 二分查找
        long long l = 0, r = m;
        while (l < r) {
            long long mid = (l + r + 1) / 2;
            if (jg[mid].g > l1) r = mid - 1;
            else l = mid;
        }
        cout << ans[l] << endl;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：

  • 两次 Dijkstra：$O((N+M)\log N)$
  • 排序：$O(M\log M)$
  • 每次询问二分：$O(\log M)$
  • 总复杂度：$O((N+M)\log N + M\log M + Q\log M)$

• 空间复杂度：$O(N+M)$

算法标签

• 图论
• 最短路径
• 二分查找
• 前缀和

总结

本题通过最短路径预处理和二分查找高效解决了路径相关的关闭费用计算问题。
核心思路是将"边是否在满足条件的路径上"转化为对边的一个关键值的比较，通过排序和前缀和优化询问回答。
该解法充分利用了最短路径的性质，将复杂的最短路径包含判断转化为简单的数值比较。