#P3081. [USACO23FEB] Moo Route II S

[USACO23FEB] Moo Route II S

题目描述

Note: The time limit for this problem is 4s, twice the default.

Bessie is on vacation! Due to some recent technological advances, Bessie will travel via technologically sophisticated flights, which can even time travel. Furthermore, there are no issues if two "parallel" versions of Bessie ever meet.

In the country there are NN airports numbered 1,2,,N1,2,\cdots ,N and MM time-traveling flights (1N,M200000)(1 \le N,M \le 200000). Flight jj leaves airport cjc_j at time rjr_j, and arrives in airport djd_j at time sj(0rj,sj109s_j (0 \le rj,sj \le 10^9, sj<rjs_j<r_j is possible)). In addition, she must leave aia_i time for a layover at airport i(1ai109)i (1 \le a_i \le 10^9). (That is to say, if Bessie takes a flight arriving in airport ii at time ss, she can then transfer to a flight leaving the airport at time rr if rs+air \ge s+a_i. The layovers do not affect when Bessie arrives at an airport.)

Bessie starts at city 11 at time 00. For each airport from 11 to NN, what is the earliest time when Bessie can get to at it?

输入格式

The first line of input contains NN and MM.

The next MM lines describe flights. The jj-th of these lines contains cj,rj,dj,sjc_j, r_j, d_j, s_j in that order. (1cj,djN,0rj,sj109)(1 \le c_j,d_j \le N, 0 \le r_j,s_j \le 10^9)

The next line describes airports. It contains NN space separated integers, a1,,aNa_1, \cdots ,a_N.

输出格式

There are NN lines of output. Line ii contains the earliest time when Bessie can get to airport ii, or 1-1 if it is not possible for Bessie to get to that airport.

题目大意

题意

Bessie 正在旅游!有 nn 个城市和 mm 条航线,第 ii 条航线有 (ci,ri,di,si)(1cidin,0ri,si109)(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) 的限制,表示从 cic_idid_i,最迟 rir_i 时进入,sis_i 时到达。第 ii 个城市有 aia_i 的停泊时间,表示 乘坐航班到达 ii 后,需要等待 aia_i 的时间后才能继续飞行。问到达每个城市的最早时间?如果不能到达,输出 -1,注意可能存在时间隧道,即到达时间sis_i可能小于出发时间rir_i

输入格式

第一行两个整数 n,mn,m

接下来 mm 行每行四个整数 ci,ri,di,sic_i,r_i,d_i,s_i

接下来一行 nn 个整数,表示 aia_i

输出格式

nn 行,第 ii 行一个整数表示到达 ii 的最早时间,不能到达输出 -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

提示

Explanation for Sample 1

Bessie can take the 33 flights in the listed order, which allows her to arrive at airports 11 and 22 at time 00, and airport 33 at time 2020.

Note that this route passes through airport 22 twice, first from time 101110-11 and then from time 010-1.

Explanation for Sample 2

In this case, Bessie can take flight 11, arriving at airport 22 at time 1010. However, she does not arrive in time to also take flight 22, since the departure time is 1010 and she cannot make a 11 time-unit layover.

SCORING

  • Inputs 353-5: rj<sjr_j<s_j for all jj , i.e. all flights arrive after they depart.
  • Inputs 6106-10: N,M5000N,M \le 5000
  • Inputs 112011-20: No additional constraints.