3872. [USACO23 Feb Silver] Moo Route II

【题目描述】

Bessie 正在旅游！有 $n$ 个城市和 $m$ 条航线，第 $i$ 条航线有 $(c_i,r_i,d_i,s_i)(1\leq c_i\neq d_i\leq n,0\leq r_i,s_i\leq 10^9)$ 的限制，表示从 $c_i$ 到 $d_i$，最迟 $r_i$ 时进入，$s_i$ 时到达。第 $i$ 个城市有 $a_i$ 的停泊时间，表示 **乘坐航班到达** $i$ 后，需要等待 $a_i$ 的时间后才能继续飞行。问到达每个城市的最早时间？如果不能到达，输出 `-1`。

【输入格式】

第一行两个整数 $n,m$。

接下来 $m$ 行每行四个整数 $c_i,r_i,d_i,s_i$。

接下来一行 $n$ 个整数，表示 $a_i$。

【输出格式】

$n$ 行，第 $i$ 行一个整数表示到达 $i$ 的最早时间，不能到达输出 `-1`。

【样例1输入】

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

【样例1输出】

0
0
20

【样例1解释】

贝茜可以按顺序依次乘坐 $3$ 个给定航班，这可以让它在时间 $0$ 到达机场 $1,2$，在时间 $20$ 到达机场 $3$。

注意，这个行进路线的过程中在机场 $2$ 停留了两次，第一次停留是时间 $10−11$，第二次停留是时间 $0−1$。

【样例2输入】

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

【样例2输出】

0
10
-1

【样例2解释】

在本样例中，贝茜可以乘坐第 $1$ 个航班并于时间 $10$ 到达机场 $2$。

然后它必须在机场 $2$ 停留时间 $1$，因此它无法乘坐第 $2$ 个航班，继而也无法乘坐第 $3$ 个航班。

【数据规模与约定】

测试点 $3-5$: $r_j<s_j$ 对于所有 $j$,即所有航班在起飞后到达。

测试点 $6-10$: $N,M \le 5000$。

$1≤N,M≤2×10^5,1≤c_j,d_j≤N,0≤r_j,s_j≤10^9,s_j<r_j$ 是有可能的。

$1≤a_i≤10^9$。