T3 - Communication 题解

题目简述

题目大意：
给定三个长度为 $N$ 的序列 $a, b, w$ 和两个参数 $L, R$。构造一张有向图，点 $u \to v$ 有边当且仅当 $L \le a_u + b_v \le R$。求从起点出发，到所有点的最短路（最短路定义为路径点权之和）。

• 数据规模：$N \le 2 \times 10^5$
• 点权限制：$w_i \ge 0$

---

子任务分析

• Subtask 1 ($N \le 7$)：极小数据，全排列或暴力搜索。
• Subtask 2 ($a_i$ 恒定)：连边具有一致性，只需判断 $a_0 + b_v$ 是否合法。
• Subtask 3 ($N \le 10^3$)：显式建边跑 Dijkstra。
• Subtask 4 ($L = 1$)：转化为前缀连边，按 $b_i$ 排序后建链优化。
• Subtask 5 ($N \le 5 \times 10^4$)：典型的线段树优化建图区间连边。

---

正解：Dijkstra + Set 优化寻点

核心算法流程

基于 Dijkstra 的贪心性质：当一个点从优先队列弹出时，其最短路已确定。我们只需解决：如何快速找到未访问且满足条件的邻居 $v$。

1. 将所有尚未确定最短路点（除了起点）存入 std::set，按 $b_i$ 值升序排列。
2. 每次从优先队列中取出当前最短路最小的点 $u$。
3. 在 set 中执行 lower_bound，定位满足 $b_v \ge L - a_u$ 的最小位置。
4. 从该位置开始向后迭代，只要满足 $b_v \le R - a_u$：
   • 更新 $v$ 的最短路。
   • 将 $v$ 加入优先队列。
   • 关键点：从 set 中永久删除 v。

#include <bits/stdc++.h>
#define uwu return 0;
using namespace std;

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    int N, L, R;
    cin >> N >> L >> R;

    vector<int> a(N), b(N);
    vector<long long> w(N);
    for(auto &i : a) cin >> i;
    for(auto &i : b) cin >> i;
    for(auto &i : w) cin >> i;

    // 按 b 值排序存储待访问点
    set <pair<int, int>> sort_by_b;
    priority_queue <pair<long long, int>> pq;
    vector <long long> dist(N, -1);
    
    for (int i = 1; i < N; i++) {
        sort_by_b.insert({b[i], i});
    }

    pq.push({-w[0], 0}); // w[0] 为起点距离，取负值用于大根堆模拟小根堆

    while(!pq.empty()){
        pair <long long, int> tp = pq.top();
        pq.pop();
        
        // 剪枝：如果已经确定过更短路径，跳过
        if (dist[tp.second] != -1 && dist[tp.second] < -tp.first) continue;
        dist[tp.second] = -tp.first;

        // 在 set 中查找 b[v] 在 [L - a[u], R - a[u]] 范围内的所有点
        auto it = sort_by_b.lower_bound({L - a[tp.second], -1});
        while (it != sort_by_b.end() && it->first + a[tp.second] <= R) {
            pq.push({tp.first - w[it->second], it->second});
            // 访问后立即删除，确保每个点只被处理一次
            it = sort_by_b.erase(it);
        }
    }

    for(int i = 0; i < N; i++) {
        cout << dist[i] << (i == N - 1 ? "" : " ");
    }
    cout << '\n';
    uwu;
}