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
  
  ........................................................................

  该题解待审

  ........................................................................(剩余 2653 个中英字符)