#PU1304. USACO 2023 February Contest, Silver — Problem 3. Moo Route II

    ID: 1405 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:feb23来源:usaco.orgscoring:equal_test_cases堆

USACO 2023 February Contest, Silver — Problem 3. Moo Route II

USACO 2023 February Contest, Silver — Problem 3. Moo Route II

题目描述

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, \ldots, N and MM time-traveling flights (1≤N,M≤2000001\leq N, M \leq 200000). Flight jj leaves airport cjc_j at time rjr_j, and arrives in airport djd_j at time sjs_j (0≤rj,sj≤1090 \leq r_j, s_j \leq 10^9, sj<rjs_j < r_j is possible). In addition, she must leave aia_i time for a layover at airport ii (1≤ai≤1091\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 r≥s+air \geq 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 jjth of these lines contains cjc_j, rjr_j, djd_j, sjs_j in that order. (1≤cj,dj≤N1\leq c_j, d_j \leq N, 0≤rj,sj≤1090\leq r_j, s_j \leq 10^9) The next line describes airports. It contains NN space separated integers, a1,…,aNa_1, \ldots, a_N.

输出格式

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

数据范围

Inputs 3-5: rj<sjr_j < s_j for all jj, i.e. all flights arrive after they depart. Inputs 6-10: N,M≤5000N, M \leq 5000 Inputs 11-20: No additional constraints. Problem credits: Brandon Wang

样例

样例 1

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10
0
0
20
Bessie can take the 3 flights in the listed order, which allows her to arrive at
airports  1 and 2 at time 0, and airport 3 at time 20.

样例 2

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10
0
10
-1
In this case, Bessie can take flight 1, arriving at airport 2 at time 10.
However, she does not arrive in time to also take flight 2, since the departure
time is 10 and she cannot make a 1 time-unit layover.

提示

then from time 0-1.