Moo Route II

题目描述

注意：本题时间限制为 4s，是默认时间限制的两倍。 Bessie 正在度假！由于一些近期的技术进步，Bessie 将乘坐高科技航班旅行，这些航班甚至可以进行时间旅行。此外，即使两条“平行”的 Bessie 相遇也不会有任何问题。

这个国家有 $N$ 个机场，编号为 $1, 2, \ldots, N$，以及 $M$ 条可进行时间旅行的航班（$1\leq N, M \leq 200000$）。第 $j$ 条航班从机场 $c_j$ 在时间 $r_j$ 起飞，并在时间 $s_j$ 到达机场 $d_j$（$0 \leq r_j, s_j \leq 10^9$，允许 $s_j < r_j$）。此外，她在机场 $i$ 中转必须预留 $a_i$ 的停留时间（$1\le a_i\le 10^9$）。 （也就是说，如果 Bessie 乘坐某航班在时间 $s$ 到达机场 $i$，那么她可以转乘一班在时间 $r$ 从该机场起飞的航班，当且仅当 $r \geq s + a_i$。中转停留时间不会影响 Bessie 到达机场的时间。）

Bessie 从城市 1 在时间 0 出发。对于从 1 到 $N$ 的每个机场，求 Bessie 最早能到达该机场的时间是多少？

输入格式

第一行包含 $N$ 和 $M$。 接下来 $M$ 行描述航班。第 $j$ 行依次包含 $c_j$、$r_j$、$d_j$、$s_j$。（$1\leq c_j, d_j \leq N$，$0\leq r_j, s_j \leq 10^9$） 下一行描述各机场。该行包含 $N$ 个用空格分隔的整数 $a_1, \ldots, a_N$。

输出格式

输出共 $N$ 行。第 $i$ 行输出 Bessie 能到达机场 $i$ 的最早时间；如果无法到达该机场，则输出 -1。

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

0
0
20

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

0
10
-1

提示

Bessie 可以按给出的顺序乘坐这 3 班航班，从而在时间 0 到达机场 1 和 2，并在时间 20 到达机场 3。 注意该路线会两次经过机场 2：第一次在时间 10-11，第二次在时间 0-1。

在这种情况下，Bessie 可以乘坐航班 1，在时间 10 到达机场 2。 然而，她无法及时乘坐航班 2，因为该航班起飞时间为 10，而她无法完成 1 个时间单位的中转停留。

SCORING: Inputs 3-5：对所有 $j$，满足 $r_j < s_j$，即所有航班都在起飞后到达。 Inputs 6-10：$N, M \leq 5000$ Inputs 11-20：无额外限制。 Problem credits: Brandon Wang

标签: USACO|2023|Silver

来源

USACO|2023|Silver