T3 - Communication 题解
题目简述
题目大意：
给定三个长度为 $N$ 的序列 $a, b, w$ 和两个参数 $L, R$。构造一张有向图，点 $u \to v$ 有边当且仅当：
$L \le a_u + b_v \le R$
求从起点出发，到所有点的最短路（路径上所有点的点权 $w_i$ 之和）。
The Key：
这是一个隐式建图的最短路问题。由于边数可能达到 $O(N^2)$，核心优化在于利用条件 $b_v \in [L - a_u, R - a_u]$ 进行区间连边或范围搜索。
子任务分析
| 子任务 | 特点 / 策略 | 复杂度 |
|---|---|---|
| Subtask 1 | $N \le 7$，全排列枚举或 DFS | $\mathcal{O}(N!)$ |
| Subtask 3 | $N \le 10^3$，直接显式建边 | $\mathcal{O}(N^2)$ |
| Subtask 5 | 线段树优化建图 | $\mathcal{O}(N \log N)$ |
正解思路：Dijkstra + 集合优化
在 Dijkstra 算法执行过程中，由于点权 $w_i \ge 0$，一旦一个点从优先队列中取出，其最短路即确定。我们不需要真的把边连出来。
执行流程：
- 将所有尚未确定最短路的点放入一个按 $b_i$ 排序的
std::set（或平衡树）。 - 从优先队列弹出当前最短路点 $u$。
- 在
set中利用lower_bound寻找满足 $b_v \ge L - a_u$ 的第一个点。 - 向后遍历
set，只要满足 $b_v \le R - a_u$：- 更新点 $v$ 的最短路。
- 将 $v$ 加入优先队列。
- 关键：将 $v$ 从
set中永久删除（因为 $v$ 的最短路已找到，不会再被其他点松弛）。
由于每个点仅被删除一次，总的时间复杂度为 $\mathcal{O}(N \log N)$。
C++ 实现代码
#include <bits/stdc++.h>
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(int &i : a) cin >> i;
for(int &i : b) cin >> i;
for(long long &i : w) cin >> i;
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});
while(!pq.empty()) {
pair<long long, int> tp = pq.top();
pq.pop();
int u = tp.second;
long long d = -tp.first;
if (dist[u] != -1) continue;
dist[u] = d;
auto it = sort_by_b.lower_bound({L - a[u], -1});
while(it != sort_by_b.end() && it->first + a[u] <= R) {
pq.push({-(d + w[it->second]), it->second});
it = sort_by_b.erase(it); // 每个点只会被删除一次
}
}
for(int i = 0; i < N; i++) cout << dist[i] << (i == N-1 ? "" : " ");
return 0;
}
1